分析：題意個人感覺比較難懂。。英語太弱。。

大意是給定一個帶有通配符的字符串，后面緊跟著列出一大堆字符串，需要你查找其中符和格式的字符串。。

根據星號所在位置對原字符串進行分割。然后通過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; }

總結

以上是生活随笔為你收集整理的UVA475 KMP算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。