在主串中找子串,输出不了第一次匹配成功的位置orz
代码如下:#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#include <iostream>
using namespace std;
typedef int Status;
#define MAXLEN 255
typedef struct{
char ch[MAXLEN+1];
int length;
}SString;
void StrAssign(SString &S)
{
int i;
char chars[MAXLEN+1];
cin>>chars;
for(i=0;chars[i]!='\0';i++)
S.ch[i]=chars[i];
S.length=i;
}
void OutString(SString S)
{
int i;
if(S.length>0)
{
for(i=0;i<S.length;i++)
printf("%c",S.ch[i]);
printf("\n");
}
}
int StrLength(SString S)
{
return S.length;
}
int Index_KMP(SString S,SString T,int nextval[])
{
int i,j;
i=1;j=1;
while(i<=S.length&&j<=T.length)
{
if(j==0||S.ch[i]==T.ch[j]){++i;++j;}
else j=nextval[j];
}
if(j>T.length)return i-T.length;
else return 0;
}
void get_nextval(SString T,int nextval[])
{
int i,j;
i=1;nextval[1]=0;j=0;
while(i<=T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
++i;++j;
if(T.ch[i]!=T.ch[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
int main()
{int a,b;
int nextval[MAXLEN+1];
SString S;
SString T;
cout<<"请输入主串S:"<<endl;
StrAssign(S);
printf("S为:");
OutString(S);
printf("串长度为:");
a=StrLength(S);
printf("%d\n",a);
printf("\n");
cout<<"请输入子串T:"<<endl;
StrAssign(T);
printf("T为:");
OutString(T);
printf("串长度为:");
b=StrLength(T);
printf("%d\n",b);
get_nextval(T,nextval);
if(Index_KMP(S,T,nextval)){
printf("子串在主串中位置为:\n");
printf("%d\n",Index_KMP(S,T,nextval));}
else printf("主串中不存在该子串");
}
比如,S为:aaaaa(5个a),T为:a,显示的位置却为5,求大神搭救,我是刚入门的小白orz