神马文学网字串定位
来源：百度文库 编辑：神马文学网 时间：2024/07/03 11:21:17
# include
# include
# include
# define MAXSTRLEN 100
int Index(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos,int &time)//返回子串T在主串S中第pos个字符之后的位置
{
int i=pos,j=1;
time=1;
while (i<=S[0]&&j<=T[0]){
if (S[i]==T[j]){
++i;
++j;
}//相等继续比较后面字符
else{
time+=1;
i=i-j+2;
j=1;
}//指针后退重新开始匹配;
}
if (j>T[0])
return i-T[0];//返回字符串的位置
else
return 0;//不存在返回0；
}//Index
int Index_KMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos,int &time,int (& next)[MAXSTRLEN])
{
int i=pos,j=1;
time=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){
++i;
++j;
}
else {
time+=1;
j=next[j];
printf("j=%d",j);
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}void get_next(char T[MAXSTRLEN],int next[MAXSTRLEN]) //求模式串T的next函数值；
{
int k,i=1,j=0;
next[1]=0;
while(i {
if(j==0||T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
for(k=1;k<=i;k++)
printf("next[%d]=%d\n",k,next[k]);
printf("\n");
}
void get_nextval(char T[MAXSTRLEN],int nextval[MAXSTRLEN])//求模式串T的next函数修正值并存入数组nextval;
{
int i=1,j=0,k;
nextval[1]=0;
while(i {
if(j==0||T[i]==T[j])
{
++i;
++j;
if (T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
for(k=1;k<=i;k++)
printf("nextval[%d]=%d\n",k,nextval[k]);
printf("\n");
}
void string_adjust(char S[MAXSTRLEN],char T[MAXSTRLEN])
{
int M,N,i;
M=strlen(S);
N=strlen(T);
for(i=M;i>=0;i--)
S[i+1]=S[i];
S[0]=M;//S[0]存放字符串M的长度；
for(i=N;i>=0;i--)
T[i+1]=T[i];
T[0]=N;//T[0]存放字符串T的长度；
}//对字符串数组进行调整；
void main()
{int f=1;
int OK,time,next[MAXSTRLEN]={0},nextval[MAXSTRLEN]={0};
char s[MAXSTRLEN] ,t[MAXSTRLEN];
while(f)
{ printf("输入主串s:");
gets(s);
printf("输入模式串t:");
gets(t);
string_adjust(s,t);
OK=Index(s,t,1,time);
printf("简单匹配算法Index的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
get_next(t,next);
get_nextval(t,nextval);
OK=Index_KMP(s,t,1,time,next);
printf("\n");
printf("KMP匹配算法Index_KMP的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
OK=Index_KMP(s,t,1,time,nextval);
printf("\n");
printf("改进后的KMP匹配算法Index_KMP的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
printf("\n");
printf("是否继续：是：输入1，否，输入0\n");
scanf("%d",&f);
if(f)
{
gets(s);
}
}
}
# include
# include
# define MAXSTRLEN 100
int Index(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos,int &time)//返回子串T在主串S中第pos个字符之后的位置
{
int i=pos,j=1;
time=1;
while (i<=S[0]&&j<=T[0]){
if (S[i]==T[j]){
++i;
++j;
}//相等继续比较后面字符
else{
time+=1;
i=i-j+2;
j=1;
}//指针后退重新开始匹配;
}
if (j>T[0])
return i-T[0];//返回字符串的位置
else
return 0;//不存在返回0；
}//Index
int Index_KMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos,int &time,int (& next)[MAXSTRLEN])
{
int i=pos,j=1;
time=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){
++i;
++j;
}
else {
time+=1;
j=next[j];
printf("j=%d",j);
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}void get_next(char T[MAXSTRLEN],int next[MAXSTRLEN]) //求模式串T的next函数值；
{
int k,i=1,j=0;
next[1]=0;
while(i
if(j==0||T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
for(k=1;k<=i;k++)
printf("next[%d]=%d\n",k,next[k]);
printf("\n");
}
void get_nextval(char T[MAXSTRLEN],int nextval[MAXSTRLEN])//求模式串T的next函数修正值并存入数组nextval;
{
int i=1,j=0,k;
nextval[1]=0;
while(i
if(j==0||T[i]==T[j])
{
++i;
++j;
if (T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
for(k=1;k<=i;k++)
printf("nextval[%d]=%d\n",k,nextval[k]);
printf("\n");
}
void string_adjust(char S[MAXSTRLEN],char T[MAXSTRLEN])
{
int M,N,i;
M=strlen(S);
N=strlen(T);
for(i=M;i>=0;i--)
S[i+1]=S[i];
S[0]=M;//S[0]存放字符串M的长度；
for(i=N;i>=0;i--)
T[i+1]=T[i];
T[0]=N;//T[0]存放字符串T的长度；
}//对字符串数组进行调整；
void main()
{int f=1;
int OK,time,next[MAXSTRLEN]={0},nextval[MAXSTRLEN]={0};
char s[MAXSTRLEN] ,t[MAXSTRLEN];
while(f)
{ printf("输入主串s:");
gets(s);
printf("输入模式串t:");
gets(t);
string_adjust(s,t);
OK=Index(s,t,1,time);
printf("简单匹配算法Index的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
get_next(t,next);
get_nextval(t,nextval);
OK=Index_KMP(s,t,1,time,next);
printf("\n");
printf("KMP匹配算法Index_KMP的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
OK=Index_KMP(s,t,1,time,nextval);
printf("\n");
printf("改进后的KMP匹配算法Index_KMP的结果:\n");
printf("比较次数为:%d\n",time);
if (OK)
printf("模式串t在主串s中的位置从第%d个字符开始,匹配成功\n",OK);
else
printf("主串S中不含模式串，模式串匹配失败\n");
printf("\n");
printf("是否继续：是：输入1，否，输入0\n");
scanf("%d",&f);
if(f)
{
gets(s);
}
}
}