KMP算法的C++代码

答案：#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void get_next(int *next,char *a,int la) /*求NEXT[]的值*/
{
     int i=1,j=0;
     next[1]=0;
     while(i<=la) /*核心部分*/
     {
        if(a[i]==a[j]||j==0)
        {
            j++;
            i++;
            if(a[i]==a[j])
               next[i]=next[j];
            else next[i]=j;       
        }
        else j=next[j];
     }
}
int  str_kmp(int *next,char *A,char *a,int lA,int la)/* EASY*/
{
     int i,j;
     i=1;
     j=1;
     while(i<=lA&&j<=la)
     {
          if(A[i]==a[j]||j==0)
          {
              i++;
              j++;
          }
          else j=next[j];   
     }
     if(j>la)
        return i-j+1;
     else  return -1;
}
int main()
{
    int k,lA=0,la=0,next[101];
    char A[101],a[101];
memset(next,0,sizeof(next));
    scanf("%s %s",A,a);
    lA=strlen(A);
    la=strlen(a);
    for(k=la-1;k>=0;k--)
       a[k+1]=a[k];
    for(k=lA-1;k>=0;k--)
        A[k+1]=A[k];
    get_next(next,a,la);
    k=str_kmp(next,A,a,lA,la);
    if(k==-1)
       printf("Not Soulation!");
    else printf("%d",k);
    return 0 ;
}const vector&lt;int&gt; * kmp_next(string &m) // count the longest prefex string ;
  {
  static vector&lt;int&gt; next(m.size());
  next[0]=0; // the initialization of the next[0];
  
 int temp; // the key iterator......
  
 for(int i=1;i&lt;next.size();i++)
  {
  temp=next[i-1];
  
 while(m[i]!=m[temp]&&temp&gt;0)
  { temp=next[temp-1];
  }
  
 if(m[i]==m[temp])
  next[i]=temp+1;
  else next[i]=0;
  
  
} 
  
return &next;
  
 }
  
  
bool kmp_search(string text,string m,int &pos)
  {
  const vector&lt;int&gt; * next=kmp_next(m);
  
 int tp=0;
  int mp=0; // text pointer and match string pointer;
  
 for(tp=0;tp&lt;text.size();tp++)
  {
  while(text[tp]!=m[mp]&&mp)
  mp=(*next)[mp-1];
  
 if(text[tp]==m[mp])
  mp++;
  
 if(mp==m.size())
  { pos=tp-mp+1;
  return true;
  }
  }
  
 if(tp==text.size())
  return false;
  }

上一个：AJAX向DIV写入HTML，但是在页面的查看源码里看不到代码
下一个：C++代码的问题