模板题。
#include <cstdio> #include <cstring> using namespace std; const int N = 1e3 + 5; char s[N], p[N]; int sl, pl, next[N]; void get_next(){ int i = 0,j = -1; next[0] = -1; while(i < pl) { if(j == -1 || p[i] == p[j]) next[++i] = ++j; else j = next[j]; } } int kmp(){ sl = strlen(s); pl = strlen(p); get_next(); int i = 0, j = 0, cnt = 0; while(j < sl){ if(i == -1 || p[i] == s[j]){ ++i; ++j; } else{ i = next[i]; } if(i == pl){ ++cnt; i = 0; } } return cnt; } int main() { while(1){ scanf("%s", s); if(strcmp(s, "#") == 0){ break; } scanf("%s", p); printf("%d\n", kmp()); } return 0; }