思路:纯kmp
#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <cstring> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; string a[1005]; int dir[4][2] = {0,1,0,-1,1,0,-1,0}; int countt,vis[1005][1005],num[1005][1005],ans[1005],sum; void getnext(char *p,int next[]) { int len = strlen(p); next[0] = -1; int k = -1; int j = 0; while(j < len -1){ if(k == -1 || p[j] == p[k]) { k++; j++; if(p[j] != p[k]) next[j] = k; else next[j] = next[k]; } else k = next[k]; } } int main() { char s[1005],p[1005]; int next[1005]; while(cin >> s){ if(s[0] == '#') break; cin >> p; getnext(p,next); int len = strlen(p),len2 = strlen(s); // for(int i=0; i<=len-1;i++) cout << next[i] << endl; int j = 0,ans = 0; for(int i = 0;i < len2;) { if(s[i] == p[j]) { i++; j++; } else { while(j!=-1 && s[i] != p[j]) j = next[j]; i++; j++; } if(j == len) { j = 0; ans++; } } cout << ans << endl; } return 0; }