裸KMP
#include <cstdio> #include <cstring> #include <iostream> #include <time.h> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; int const MAXN = 1000010; char s[MAXN],s1[MAXN]; int next[MAXN]; inline void Get_Next(int n){ memset(next,0,sizeof(next)); for(int i = 1;i < n;i++){ int j = next[i]; while(j && s[i] != s[j]) j = next[j]; if(s[i] == s[j]) next[i + 1] = j + 1; else next[i + 1] = 0; } } inline void Kmp(int n,int m){ Get_Next(m); int j = 0,cnt = 0; for(int i = 0;i < n;i++){ while(j && s[i] != s1[j]) j = next[j]; if(s[i] == s1[j])j++; if(j == m){ cnt++; j = 0; } } printf("%d\n",cnt); } int main(){ int T,k = 1; while(cin>>s){ if(s[0] == '#') break; scanf("%s",s1); int m = strlen(s1),n = strlen(s); Kmp(n,m); } return 0; }