请大家点评,谢谢!!!
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include<iostream>
using namespace std;
const int MAXSIZE=32;
//#define MAXSIZE 32
//定义结构体
struct stack_ch
{
char ch[MAXSIZE];
int Length;
};
//求next函数值
void GetNext(stack_ch &ch,int m,int *next,int n)
{
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,int m)
{
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,int m)
{
//利用模式串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]={0},pos,pos2;
cout<<"输入主串:(end by '*')"<<endl;
//输入主串
Enter_stack(S,next,MAXSIZE);
cout<<"输入模式串:(end by '*')"<<endl;
//输入模式串
Enter_stack(T,next,MAXSIZE);
GetNext(T,MAXSIZE,next,MAXSIZE);
cout<<"输入pos的值(1<=pos<=S.Length)S是主串:"<<endl;
//输入pos值
cin>>pos;
pos2=Index_KMP(S,T,pos,next,MAXSIZE);
//输出所求的位置值
cout<<"The position is:"<<pos2<<endl;
system("pause");
return 0;
}
2008-05-25 11:15
[color=white]