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));
    }
}