KMP的一点心得

时间:2023-01-16 11:11:29
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++;