[收集]]关于KMP算法!
关于KMP.老实说,我是看了至少四遍才基本理解它的整个推导过程,真是菜也.第一遍连看下去的耐心都没有,第二遍看着看着干脆去吃饭了,直到第三遍,第四遍,做了练习之后,情况才有所好转...呵呵..
个人理解KMP的主要思想就是 : 模式串在跟主串匹配的时候主串的指针不回溯。至于它的推导过程,很多书上都有详细过程,我就不多说了,这里给出我写的一个代码,代码有注释，应该能看明白吧!也请大家把自已写过的关于模式匹配的代码共享出来.让我对这个算法的应用有更多的了解,谢谢！！！
my code:
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include<iostream>
#define MAXSIZE 32
using namespace std;
//定义结构体
struct stack_ch
{
char ch[MAXSIZE];
int Length;
};
//求next函数值
void GetNext(stack_ch ch,int next[MAXSIZE])
{
int i=1,j=0;
next[1]=0;
while (i<ch.Length)
{
if (j==0 || ch.ch[i]==ch.ch[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}//Get_next
//输入字符串
void Enter_stack(stack_ch &ch,int next[MAXSIZE])
{
char data;
ch.Length=0;
cin>>data;
while (data!='*')
{
ch.ch[++ch.Length]=data;
cin>>data;
}
}
//将模式串和主串进行匹配操作，返回模式串在主串S第pos个字符之后可匹配的位置
int Index_KMP(stack_ch S,stack_ch T,int pos,int next[MAXSIZE])
{
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置,T非空且1<=pos<=S.Length
int i=pos,j=1;
while (i<=S.Length && j<=T.Length) //对两串扫描
{
if (j==0 || S.ch[i]==T.ch[j]) //对应字符匹配
{
i++;
j++;
}
else
j=next[j];
}
if (j>T.Length)
return (i-T.Length); //匹配成功
else
return 0; //匹配失败
} //Index_KMP
int main(void)
{
stack_ch S,T;
int next[MAXSIZE],pos,pos2;
cout<<"输入主串:(end by '*')"<<endl;
//输入主串
Enter_stack(S,next);
cout<<"输入模式串:(end by '*')"<<endl;
//输入模式串
Enter_stack(T,next);
GetNext(T,next);
cout<<"输入pos的值(1<=pos<=S.Length)S是主串:"<<endl;
//输入pos值
cin>>pos;
pos2=Index_KMP(S,T,pos,next);
//输出所求的位置值
cout<<"The position is:"<<pos2<<endl;
system("pause");
return 0;
}
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include<iostream>
#define MAXSIZE 32
using namespace std;
//定义结构体
struct stack_ch
{
char ch[MAXSIZE];
int Length;
};
//求next函数值
void GetNext(stack_ch ch,int next[MAXSIZE])
{
int i=1,j=0;
next[1]=0;
while (i<ch.Length)
{
if (j==0 || ch.ch[i]==ch.ch[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}//Get_next
//输入字符串
void Enter_stack(stack_ch &ch,int next[MAXSIZE])
{
char data;
ch.Length=0;
cin>>data;
while (data!='*')
{
ch.ch[++ch.Length]=data;
cin>>data;
}
}
//将模式串和主串进行匹配操作，返回模式串在主串S第pos个字符之后可匹配的位置
int Index_KMP(stack_ch S,stack_ch T,int pos,int next[MAXSIZE])
{
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置,T非空且1<=pos<=S.Length
int i=pos,j=1;
while (i<=S.Length && j<=T.Length) //对两串扫描
{
if (j==0 || S.ch[i]==T.ch[j]) //对应字符匹配
{
i++;
j++;
}
else
j=next[j];
}
if (j>T.Length)
return (i-T.Length); //匹配成功
else
return 0; //匹配失败
} //Index_KMP
int main(void)
{
stack_ch S,T;
int next[MAXSIZE],pos,pos2;
cout<<"输入主串:(end by '*')"<<endl;
//输入主串
Enter_stack(S,next);
cout<<"输入模式串:(end by '*')"<<endl;
//输入模式串
Enter_stack(T,next);
GetNext(T,next);
cout<<"输入pos的值(1<=pos<=S.Length)S是主串:"<<endl;
//输入pos值
cin>>pos;
pos2=Index_KMP(S,T,pos,next);
//输出所求的位置值
cout<<"The position is:"<<pos2<<endl;
system("pause");
return 0;
}
[ 本帖最后由 zjl138 于 2008-5-24 18:09 编辑 ]
