#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#define N 255
using namespace std;
typedef char SString[N+1];
SString T,S;
void GetNext(SString &T,int *next) {
int i=1,j=0;
next[i]=0;
while(i<T[0])
if(j==0||T[i]==T[j]){
++i;++j;
next[i]=j;}
else j=next[j];
}
int IndexKMP(SString &S,SString &T,int *next) {
int i=1,j=1;
while(i<S[0]||j<T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>T[0]) return i-T[0];
else return 0;
}
void all(SString &S){
int i=0,j=1;
if(S[j]!=NULL) i++;
S[0]=i;
}
void main(){
int k;
int next[N];
gets(&S[1]);
all(S);
gets(&T[1]);
all(T);
GetNext(T,next);
k=IndexKMP(S,T,next);
cout<<k;
}

void all(SString &S){
int i=0,j=1;
if(S[j]!=NULL) i++;
S[0]=i;
}

while(S[j] != NULL) j++,i++;

粗心

还是不行

#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#define N 255
using namespace std;
typedef char SString[N+1];
SString T,S;
void GetNext(SString &T,int *next) {
int i=1,j=0;
next[i]=0;
while(i<T[0])
if(j==0||T[i]==T[j]){
++i;++j;
next[i]=j;}
else j=next[j];
}
int IndexKMP(SString &S,SString &T,int *next) {
int i=1,j=1;
while(i<S[0]||j<T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>T[0]) return i-T[0];
else return 0;
}
void all(SString &S){
int i=0,j=1;
while(S[j] != NULL) {
j++,i++;
}
S[0]=i;
}
void main(){
int k;
int next[N];
gets(&S[1]);
all(S);
gets(&T[1]);
all(T);
GetNext(T,next);
k=IndexKMP(S,T,next);
cout<<k;
}


输入abcdabcde
abcde
输出是0

typedef char SString[N+1];
SString T,S;
void GetNext(SString T,int *next) {
int i=1,j=0;
next[i]=0;
while(i<T[0])
if(j==0 || T[i]==T[j]){
++i;++j;
next[i]=j;
}
else j=next[j];
}

int IndexKMP(SString S,SString T,int *next) {
int i=1,j=1;
while(i<S[0]||j<T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>=T[0]) return i-T[0]+1;
else return 0;
}
void all(SString S){
int i=0,j=1;
while(S[j]!=NULL) j++,i++;
S[0]=i;
}
void main(){
int k;
int next1[N];
gets(&S[1]);
all(S);
gets(&T[1]);
all(T);
GetNext(T,next1);
k=IndexKMP(S,T,next1);
cout<<k;
}

#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#define N 255
using namespace std;
typedef char SString[N+1];
SString T,S;
void GetNext(SString T,int *next) {
int i=1,j=0;
next[i]=0;
while(i<T[0])
if(j==0 || T[i]==T[j]){
++i;++j;
next[i]=j;
}
else j=next[j];
}

int IndexKMP(SString S,SString T,int *next) {
int i=1,j=1;
while(i<S[0]||j<T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>=T[0]) return i-T[0]+1;
else return 0;
}
void all(SString S){
int i=0,j=1;
while(S[j]!=NULL) {
j++; i++;
}
S[0]=i;
}
void main(){
int k;
int next[N];
cout<<"请输入字符串S:"<<endl;
gets(&S[1]);
all(S);
cout<<"请输入字符串T:"<<endl;
gets(&T[1]);
all(T);
GetNext(T,next);
k=IndexKMP(S,T,next);
cout<<"从第";
cout<<k;
cout<<"个字符发现匹配"<<endl;
}

子串若在中间好象不行,会说程序有问题
例如情况

子串在中间不行,
abcabcdabcde
abcd
会弹出错误窗口.

int IndexKMP(SString S,SString T,int *next) {
int i=1,j=1;
while(i<=S[0] && j<=T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>T[0]) return i-j+1;
else return 0;
}

十分感谢你,书上的算法居然也有问题

匹配可以,但怎么输出next的值有点不对
比如子串是abcdeabcdef


#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#define N 255
using namespace std;
typedef char SString[N+1];
SString T,S;
void GetNext(SString T,int *next) {
int i=1,j=0;
next[i]=0;
while(i<T[0]){
if(j==0 || T[i]==T[j]){
++i;++j;
next[i]=j;
}
else j=next[j];
}
for(i=0;i<T[0];i++){
cout<<next[i+1];
cout<<" ";
}
cout<<endl;
}

int IndexKMP(SString S,SString T,int *next) {
int i=1,j=1;
while(i<=S[0] && j<=T[0])
if(j==0||S[i]==T[j]){
++i;++j;
}
else j=next[j];
if(j>T[0]) return (i-j+1);
else return 0;
}
void all(SString S){
int i=0,j=1;
while(S[j]!=NULL) {
j++; i++;
}
S[0]=i;
}
void main(){
int k,i;
int next[N];
cout<<"请输入字符串S:"<<endl;
gets(&S[1]);
all(S);
cout<<"请输入字符串T:"<<endl;
gets(&T[1]);
all(T);
cout<<"next值分别为:";
GetNext(T,next);
k=IndexKMP(S,T,next);
cout<<"在第";
cout<<k;
cout<<"个字符发现匹配"<<endl;
}