对于本文的KMP算法,你需要看看这些文章《数据结构作业之串实现通信录》《KMP算法之next数组的简便求解》。另外,对于本文的代码,是摘抄自书上的,没有什么可讲的,要是不懂的话,自己看数据结构的书来理解吧。
先看看实现:
代码:
#include "iostream"
#include "windows.h"
using namespace std;
typedef struct
{
char str[60];
int length;
}SeqString;
void StrAssign(SeqString *s, char cstr[])
{
int i=0;
for (;cstr[i]!='\0'; i++)
{
s->str[i]=cstr[i];
}
s->length=i;
}
int GetNext(SeqString T, int next[])
{
int j=0;
int k=-1;
next[0]=-1;
while (j<T.length)
{
if (k==-1 || T.str[j]==T.str[k])
{
j++;
k++;
next[j]=k;
}
else
{
k=next[k];
}
}
return 1;
}
int KMP_Index(SeqString S,int pos, SeqString T, int next[])
{
int i,j;
i=pos-1;
j=0;
while (i<S.length && j<T.length)
{
if (j==-1 || S.str[i]==T.str[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if (j>=T.length)
{
return i-T.length+1;
}
else
{
return -1;
}
}
int StrLength(SeqString s)
{
return s.length;
}
int main()
{
SeqString s,t;
int find,num;
int next[40];
char tongxunlu[10][40];
char chazhao[40];
cout<<"-------------------------------利用KMP算法建立通讯录信息------------------------"<<endl;
cout<<"-------------------------------输入通讯录的人员个数:----------------------------"<<endl;
cout<<" 通讯录的人员有:";
cin>>num;
cout<<endl;
cout<<"-------------------------------通讯录的通讯信息:--------------------------------";
for (int i=0; i<num; i++)
{
cin>>tongxunlu[i];
}
cout<<"-------------------------------建立通讯录完毕-----------------------------------"<<endl;
cout<<"-------------------------------输入你要查找的通讯人的名字:";
cin>>chazhao;
for (int i=0; i<num; i++)
{
StrAssign(&s,tongxunlu[i]);
StrAssign(&t,chazhao);
GetNext(t,next);
find=KMP_Index(s,1,t,next);
if (find > 0)
{
cout<<"-------------------------------查找的人的通讯信息:------------------------------"<<endl;
cout<<" "<<tongxunlu[i]<<endl;
}
}
system("pause");
return 0;
}