int next[] //next数组储存的是当模式串匹配不上的时候将要跳转的下标
void getnext(char b[])
{
next[0]=-1;
for(int i=1,j=0;b[i];i++)
{
next[i]=j;
while(j>=0&&b[i]!=b[j])j=next[j];
j++;
}
}
int kmp(char a[],char b[])//寻找主串中有多少模式串
{
int k=0;
for(int i=0,j=0;a[i];i++)
{
while(j>=0&&b[j]!=a[i])j=next[j];
j++;
if(b[j]=='\0')
{
k++;
j=nextp[j-1];
while(j>=0&&a[i]!=b[j])j=next[j];
j++;
}
}
return k;
}
int kmp(char a[],char b[])//判断主串中是否有模式串
{
for(int i=0,j=0;a[i];i++)
{
while(j>=0&&b[j]!=a[i])j=next[j];
j++;
if(b[j]=='\0')return 1;
}
return 0;
}
字符串a代表的是主串 b代表的是模式串；
思路：
先对next[0]赋值-1；
每次对下一个进行操作的时候先对next进行赋值 --> next[i]=j;
然后当两个字符匹配不上的时候 利用递归的思想去next数组里面寻求将要跳转的下标 --> j=next[j];
先进行赋值 再进行比较的操作，
只有当j==-1 或者两个字符相等的时候才会跳出循环，所以每次跳出的时候将j++，如果跳出的时候满足j==-1
那么j++可以将j重新赋值为0.如果相等的情况下跳出 那么对于两个字符串都要比较下一个字符--->i++,j++;