|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> using namespace std; vector<int> getNext(char* str){ int len = strlen(str); vector<int> lt; lt.push_back(0); //cout << 0 << endl; for (int i = 1;i < len;i++) { if(str[lt[i-1]] == str[i]){ lt.push_back(lt[i-1]+1); }else{ lt.push_back(0); } //cout << lt[i] << endl; } return lt; } int main(int argc, char *argv[]) { int cnt = 0; cin >> cnt; while (cnt--) { char a[10005],b[1000005]; scanf(" %s %s",a,b); vector<int> lt = getNext(a); int lena = strlen(a),lenb = strlen(b); int cura = 0,curb = 0,res = 0; while(curb < lenb){ //cout << "^" << curb << "!" << cura << endl; while (cura < lena && curb < lenb){ //cout << "!" << cura << endl; if(b[curb] == a[cura]){ cura++,curb++; }else{ if(cura == 0) curb++; else cura = lt[cura-1]; } } if (curb >= lenb && cura != lena) break;//failed if(cura == lena){//success //cout << "get" << curb << endl; res++; cura = lt[cura-1]; } } cout << res << endl; } return 0; } |
在标准KMP的基础上，在匹配完后，继续匹配而不停止，只是给计数器加一下。
第一次自己写KMP，我已逼实。