kmp轻改
这里有一个条件就是我们在kmp匹配时,匹配的子串不能交错。
很简单稍微改一下就可以了。
当我们匹配成功时,直接让j=0从头开始匹配就好了。
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int net[1100]; void getnext(char p[],int size) { int i = 0;int j = -1; net[0] = -1;net[size]=(char)500;//绝对不会出现的数 while (i < size) { if (j == -1 || p[i] == p[j]) { ++i;++j; if (p[i] != p[j]) net[i] = j; else net[i] = net[j]; } else j = net[j]; } } int kmp(char s[],int ssize,char p[],int psize) { register int i = 0;register int j = 0; int res = 0; while (i < ssize) { if (j == -1 || p[j] == s[i]) { ++i;++j; } else j = net[j]; if (j == psize) { ++res; j = 0; } }return res; } char s[1100],p[1100]; int main(){ while (scanf("%s",s)){ int n = strlen(s); if (n==1&&s[0]=='#')break; scanf("%s",p); int m = strlen(p); getnext(p,m); printf("%d\n",kmp(s,n,p,m)); } }