1、建立目標(biāo)串s和模式串t
2、采用簡(jiǎn)單算法求t在s中的位置
3、由模式串t求出next值和nextval值
4、采用KMP算法和KMP改進(jìn)算法求t在s中的位置
代碼如下：
#include<stdio.h>
#include<string.h>
#define MaxSize 100
typedef struct
{
?char ch[MaxSize];
?int len;
}SqString;
int Index(SqString s,SqString t)/* 簡(jiǎn)單匹配方法*/
{
? int i=0,j=0,k;
? while(i<s.len&&j<t.len)
? {
??? if(s.ch[i]==t.ch[j])/*繼續(xù)匹配下一個(gè)字符*/
?{
?? i++;
?? j++;
?}
?else/*子串、主串的指針回溯重新開(kāi)始下一次匹配*/
?{
? i=i-j+1;
? j=0;
?}
? }
? if(j>=t.len)/*匹配成功，返回匹配的第一個(gè)字符下標(biāo)*/
?? k=i-t.len;
? else/*匹配不成功*/
?? k=-1;
? return k;
}
void GetNext(SqString t,int next[])/*由模式串t求出next值*/
{
?int j,k;
?j=0;k=-1;next[0]=-1;
?while(j<t.len-1)
?{
?? if(k==-1||t.ch[j]==t.ch[k])
?? {
???? j++;k++;
???? next[j]=k;
?? }
?? else k=next[k];
?}
}
void GetNextval(SqString t,int nextval[])/*由模式串t求出nextval值*/
{
?? int j=0,k=-1;
?? nextval[0]=-1;
?? while(j<t.len)
?? {
??? if(k==-1||t.ch[j]==t.ch[k])
??? {
????? j++;k++;
?? if(t.ch[j]!=t.ch[k])
??
??? nextval[j]=k;
?? else
?????? nextval[j]=nextval[k];
?? }
?? else k=nextval[k];
???
?? }
}
int KMPIndex(SqString s,SqString t)/*KMP算法*/
{
?? int next[MaxSize];
?? int i=0,j=0;
?? int v;
?? GetNext(t,next);
?? while(i<s.len && j<t.len)
?? {
???? if(j==-1||s.ch[i]==t.ch[j])
???? {
???? ?i++;
???? ?j++;
?? }
?? else j=next[j];
?? }
?? if(j>=t.len)
?? v=i-t.len;
?? else
?? v=-1;
?? return v;
}
int KMPIndex1(SqString s,SqString t)/*改進(jìn)的KMP算法*/
{
?int nextval[MaxSize],next[MaxSize],i=0,j=0,v;
?GetNextval(t,next);
?GetNextval(t,nextval);
?while(i<s.len&&j<t.len)
?{
? if(i==-1||s.ch[i]==t.ch[j])
? {
??? i++;
?j++;
? }
? else j=nextval[j];
?}
?if(j>=t.len)
? v=i-t.len;/*返回匹配模式串的首字符下標(biāo)*/
?else
? v=-1;
?return v;
}
void StrAssign(SqString &str,char cstr[])/*由串常量cstr創(chuàng)建串str */
{
?? int i;
?? for(i=0;cstr[i]!='\0';i++)
??? str.ch[i]=cstr[i];
?? str.len=i;
}
void DispStr(SqString s)/*輸出串s的所有元素*/
{
? int i;
? if(s.len>0)
? {
??? for(i=0;i<s.len;i++)
??printf("%c",s.ch[i]);
?printf("\n");
? }
}
void main()
{
? int j;
? int next[MaxSize],nextval[MaxSize];
? SqString s,t;
? StrAssign(s,"abcabcdabcdeabcdefabcdefg");
? StrAssign(t,"abcdeabcdefab");
? printf("串s:");DispStr(s);
? printf("串t:");DispStr(t);
? printf("簡(jiǎn)單匹配P算法:\n");
? printf("t在s中的位置:%d\n",Index(s,t));
? GetNext(t,next);
? GetNextval(t,nextval);
? printf(" j???? ");
? for(j=0;j<t.len;j++)
? {
?? printf("%4d",j);
? }
? printf("\n");
? printf("t[j]?? ");
? for(j=0;j<t.len;j++)
? printf("%4c",t.ch[j]);
? printf("\n");
? printf("next?? ");
? for(j=0;j<t.len;j++)
? printf("%4d",next[j]);
?? printf("\n");
??
?? printf("nextval");
?? for(j=0;j<t.len;j++)
?? printf("%4d",nextval[j]);
?? printf("\n");
?? printf("KMP算法:\n");
?? printf("t在s中的位置:%d\n",KMPIndex(s,t));
?? printf("改進(jìn)的KMP算法:\n");
?? printf("t在s中的位置:%d\n",KMPIndex1(s,t));
}
結(jié)果如下：
串s:abcabcdabcdeabcdefabcdefg
串t:abcdeabcdefab
簡(jiǎn)單匹配P算法:
t在s中的位置:7
?j??????? 0?? 1?? 2?? 3?? 4?? 5?? 6?? 7?? 8?? 9? 10? 11? 12
t[j]????? a?? b?? c?? d?? e?? a?? b?? c?? d?? e?? f?? a?? b
next???? -1?? 0?? 0?? 0?? 0?? 0?? 1?? 2?? 3?? 4?? 5?? 0?? 1
nextval? -1?? 0?? 0?? 0?? 0? -1?? 0?? 0?? 0?? 0?? 5? -1?? 0
KMP算法:
t在s中的位置:7
改進(jìn)的KMP算法:
t在s中的位置:7