分析：题意个人感觉比较难懂。。英语太弱。。
大意是给定一个带有通配符的字符串，后面紧跟着列出一大堆字符串，需要你查找其中符和格式的字符串。。
根据星号所在位置对原字符串进行分割。然后通过KMP算法进行匹配。
特别注意的是如果没有一个符合条件的字符串，那么不输出任何东西，换行也免了。
代码如下：
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <string> #include <iostream> using namespace std; const int maxn = 1e6+10; string s,file; vector<string>origin; vector<string>answer; int Next[maxn]; int Left,Right; bool isFirst; bool F; bool flag; void init(){ origin.clear(); string tmp = ""; F = 0; for (int i=0; i<s.length(); i++) { if (s[i]=='*') { F = 1; if (tmp!="") origin.push_back(tmp); tmp = ""; continue; } tmp += s[i]; } if (tmp!="") origin.push_back(tmp); Left = 0; Right = origin.size(); if (s[0]!='*') Left++; if (s[s.length()-1]!='*') Right--; } void Print(){ if (flag) { if (!isFirst) printf("\n"); isFirst = 0; cout << "MATCHES FOR THE PATTERN: " << s << endl; for (int i=0; i<answer.size(); i++) cout <<answer[i] << endl; } } void get_next(string x){ Next[0] = Next[1] = 0; int j = 0; for (int i=1; i<x.length(); i++) { while (j && x[j]!=x[i]) j = Next[j]; if (x[j]==x[i]) j++; Next[i+1] = j; } } bool kmp(string x){ int u = Left, j = 0; if (u==Right) return 1; for (int i=0; i<x.length(); i++) { while (j && x[i]!=origin[u][j]) j = Next[j]; if (x[i]==origin[u][j]) j++; if (j==origin[u].length()) { u++; j=0; } if (u==Right) return 1; } return 0; } bool judge(){ if (!F) return file == origin[0]; int l = 0, r = file.length()-1; if (s[s.length()-1]!='*') { string s1 = origin[origin.size()-1]; for (int i=s1.length()-1; i>=0; i--) { if (file[r]!=s1[i]) return 0; r--; } } if (s[0]!='*') { string s1 = origin[0]; for (int i=0; i<s1.length(); i++) { if (file[l]!=s1[i]) return 0; l++; } } string tmp =""; for (int i=l; i<=r; i++) tmp += file[i]; get_next(tmp); if (kmp(tmp)) return 1; return 0; } int main(){ isFirst = 1; while (getline(cin,s)){ init(); flag = 0; answer.clear(); while (getline(cin,file)){ if (file=="") break; if (judge()) { flag = 1; answer.push_back(file); } } Print(); } return 0; }
