《数据结构》读书笔记 第四章 KMP算法

半懂不懂,大概能明白……程序是写出来了。

#include <iostream>
enum {MSL=100};

char S[MSL+1];
char T[20];
int next[20];
using namespace std;

void StrSet(char *S,char *T)
{
 S[0]=strlen(T);
 int i;
 if(S[0]<=MSL)
 {
  for(i=1;i<=S[0];i++)
   S[i]=T[i-1];
 }
 else
 {
  for(i=1;i<=MSL;i++)
   S[i]=T[i-1];
  S[0]=MSL;
 }
}

void StrPrint(char *S)
{
 cout<<"打印字符串:";
 int i;
 for(i=1;i<=S[0];i++)
  cout<<S[i];

 cout<<endl;
}

void Next(char *T,int *next)
{
 int i=1,j=0;
 while(i<T[0])
  if(j==0||T[i]==T[j])
  {
   i++;
   j++;
   next[i]=j;
  }
  else
   j=next[j];
}

void GetNext(char *T,int *next)
{
 int i=1,j=0;
 next[1]=0;
 while(i<T[0])
 {
  if(j==0||T[i]==T[j])
  {
   i++;
   j++;
   if(T[i]!=T[j])
    next[i]=j;
   else
    next[i]=next[j];
  }
  else
   j=next[j];
 }
}

int KMP(char *S,char *T,int *next)
{
 int i=1,j=1;
 while(i<=S[0]&&j<=T[0])
 {
  if(S[i]==T[j]||j==0)
  {
   i++;
   j++;
  }
  else
   j=next[j];
 }
 if(j>T[0])
  return i-T[0];
 else
  return 0;
}

int main()
{
 int i;
 StrSet(S,"aaabaaaab");
 cout<<"主串为,";
 StrPrint(S);
 StrSet(T,"aaaab");
 cout<<"子串为,";
 StrPrint(T);
 GetNext(T,next);
 cout<<"";
 cout<<"nextval数组为:";
 for(i=1;i<=T[0];i++)
  cout<<next[i]<<" ";
 cout<<endl;
 cout<<"找到的位置为:";
 cout<<KMP(S,T,next)<<endl;

 Next(T,next);
 cout<<"next数组为:";
 for(i=1;i<=T[0];i++)
  cout<<next[i]<<" ";
 cout<<endl;
 cout<<"找到的位置为:";
 cout<<KMP(S,T,next)<<endl;
}

Leave a Reply

Your email address will not be published.