UVa 475 Wild Thing

题目描述

题目要求判断给定的文件名是否匹配包含通配符*的模式。*可以匹配零个或多个任意字符（包括空字符串）。模式中可能包含多个*。输入包含多个数据集，每个数据集由一行模式字符串和若干行文件名组成，文件名列表以空行结束。输出所有匹配该模式的文件名。

输入格式

输入包含多个数据集。每个数据集的第一行为模式字符串（可能包含*），随后若干行为文件名（不含*），每行一个。文件名列表以空行结束。数据集之间由一个空行分隔。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个至少有一个匹配文件名的数据集，输出一行MATCHES FOR THE PATTERN: 模式，然后每行输出一个匹配的文件名。两个数据集的输出之间由一个空行分隔。若某数据集没有匹配的文件名，则不输出任何内容。

样例

输入

C*AT COMFILE.DAT COST.DATA CAT %XCAT COAT CATCH *A* MOUNTAIN.TXT ALFRED PROG1A SECOND.ED PROG1A.PAS HELLO NOTHING B**N* NIBBLE.BIT BANANA BNXJ.25 BORN ABNORMAL.LIS BRANDISH.SRD BITNET

输出

MATCHES FOR THE PATTERN: C*AT COMFILE.DAT CAT COAT MATCHES FOR THE PATTERN: *A* MOUNTAIN.TXT ALFRED PROG1A PROG1A.PAS MATCHES FOR THE PATTERN: B**N* BANANA BNXJ.25 BORN BRANDISH.SRD BITNET

题目分析

本题的核心是通配符匹配（*匹配零个或多个字符）。由于模式长度和文件名长度均不超过202020，可以使用递归搜索（DFS\texttt{DFS}DFS）或动态规划求解。

匹配算法

采用双指针递归方法：

• 将模式按*分割成若干段（连续的非*字符段）。
• 在文件名中顺序查找这些段，且段之间可以间隔任意字符（由*匹配）。
• 最后一个*之后的部分必须匹配文件名的末尾。

具体递归函数dfs(pl, pr, fl, fr)\texttt{dfs(pl, pr, fl, fr)}dfs(pl, pr, fl, fr)表示匹配模式子串[pl,pr)[\textit{pl}, \textit{pr})[pl,pr)与文件名字串[fl,fr)[\textit{fl}, \textit{fr})[fl,fr)：

• 若pl==pr\textit{pl} == \textit{pr}pl==pr且fl==fr\textit{fl} == \textit{fr}fl==fr，匹配成功。
• 若pl<pr\textit{pl} < \textit{pr}pl<pr且当前字符为*：
  • 找到下一个非*段（长度LLL）。
  • 在文件名中从fl\textit{fl}fl开始寻找该段的所有出现位置，递归匹配剩余部分。
• 若当前字符不为*：
  • 找到下一个*或结尾，得到一段连续非*字符段（长度LLL）。
  • 若文件名剩余长度足够且该段匹配，则继续递归。

连续*处理

多个连续的*等同于一个*，可先压缩模式，将连续*替换为单个*。

边界情况

• 模式为*时，匹配所有文件名。
• 模式开头或结尾的*分别匹配文件名的前缀或后缀。

复杂度分析

模式长度Lp≤20L_p \le 20Lp​≤20，文件名长度Lf≤20L_f \le 20Lf​≤20，递归搜索状态有限，可接受。

代码实现

// Wild Thing// UVa ID: 475// Verdict: Accepted// Submission Date: 2019-01-21// UVa Run Time: 0.000s//// 版权所有（C）2019，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;booldone;string pattern,filename;voiddfs(intpl,intpr,intfl,intfr){if(pl==pr&&fl==fr){done=true;return;}if(pl<pr&&pattern[pl]=='*'){intx=0;for(x=pl+1;x<pr&&pattern[x]!='*';x++);intL=x-pl-1;for(inti=fl;i+L<=fr;i++){if(pattern[pl+1]!=filename[i])continue;if(pattern.substr(pl+1,L)==filename.substr(i,L))dfs(pl+L+1,pr,i+L,fr);if(done)return;}}elseif(pl<pr&&pattern[pl]!='*'){intx=0;for(x=pl+1;x<pr&&pattern[x]!='*';x++);intL=x-pl;if(fl+L<=fr&&pattern.substr(pl,L)==filename.substr(fl,L))dfs(pl+L,pr,fl+L,fr);if(done)return;}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;while(getline(cin,pattern)){string backup=pattern;for(inti=pattern.size()-1;i>0;i--)if(pattern[i]=='*'&&pattern[i-1]=='*')pattern.erase(pattern.begin()+i);vector<string>matched;while(getline(cin,filename),filename.length()>0){done=false;if(pattern=="*")done=true;if(!done)dfs(0,pattern.size(),0,filename.size());if(done)matched.push_back(filename);}if(matched.size()>0){if(cases++)cout<<'\n';cout<<"MATCHES FOR THE PATTERN: "<<backup<<'\n';for(autom:matched)cout<<m<<'\n';}}return0;}