KMP模板
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include <vector> using namespace std; int m,n; int ans; char a[10007],b[10007]; int nex[10007]; void getnext()//求子串的next数组 { int i = 1, j = 0; while(i < m) { if(j == 0 && b[i] != b[j]) { nex[i] = 0; i ++; } else if(j > 0 && b[i] != b[j]) j = nex[j-1]; else { nex[i] = j + 1; i ++; j ++; } } } int kmp() { int i = 0,j = 0; while(i < n && j < m) { if(j == 0 && a[i] != b[j]) i ++; else if(j > 0 && a[i] != b[j]) j = nex[j-1]; else { i ++; j ++; }//查找相同部分 if(j == m) { ans++; j=0;//求不重叠的子串个数,若判断有没有子串,直接输出ans,若重叠的子串个数,不用对j赋值,输出ans,若输出起始位置,i-j+1; } } return ans; } int main() { while(~scanf("%s",&a)&&a[0]!='#') { scanf("%s",&b); ans=0; m=strlen(b); n=strlen(a); getnext(); kmp(); printf("%d\n",ans); } return 0; }