#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"
#define MAXSTRLEN 100
#define OK 1
#define NULL 0
using namespace std
typedef char SString[MAXSTRLEN+1]
SString T,S
int next[MAXSTRLEN],c[MAXSTRLEN]
int i,j
void get_next(SString &T,int next[MAXSTRLEN]){
i=1next[1]=0j=0
while(i<T[0]){
if(j==0||T[i]==T[j]){++i++jnext[i]=j}
else j=next[j]
}
}
int KMP(SString &S,SString &T){
i=1j=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 main(){
int k,p=1
int i=1,j=1
printf("输入主串：")
gets(&M[1])
printf("输入模式串：")
gets(&N[1])
while(M[i]!=NULL)
{
i++
M[0]=i-1
}
puts(&M[1])
while(N[j]!=NULL)
{
j++
N[0]=j-1
}
puts(&N[1])
if(M[0]>N[0])
{
printf("error!")
exit(0)
}
get_next(T,next)
for(i=1i<=T[0]i++)printf("%d",next[i])
printf("\n")
k=KMP(S,T)
printf("模式串从主串第%d个开始匹配！",k)
}
KMP算法的C语言实现2007-12-10 23:33基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos)
void get_next(char *t,int *)
char s[10]="abcacbcba"
char t[4]="bca"
int next[4]
int pos=0
int main()
{
int n
get_next(t,next)
n=index_KMP(s,t,pos)
printf("%d",n)
return 0
}
int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++
j++
}
else j=next[j]
}
if (j>(int)strlen(t))
return i-strlen(t)+1
else
return 0
}
void get_next(char *t,int *next)
{
int i=1,j=0
next[0]=next[1]=0
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++
j++
next[i]=j
}
else j=next[j]
}
}
问题出在void StrCreate(Sqstring *s)这个函数中，你在函数内给形参malloc内存，这些内存在函数返回时会被回收，因此相当于你没有分配内存。
解决的方法就是在main中分配内存，而不是在create中，或者也可以将create函数改一下：
Sqstring *StrCreate()
{
int i
s=(Sqstring*)malloc(sizeof(Sqstring))
printf("请输入字符串(长度不超过%d)!\n",Maxsize)
for(i=0i<Maxsizei++)
{
scanf("%c",s->data[i])
if(s->data[i]=='1')
break
}
s->length=i
return s
}
调用时先声明一个串指针
Sqstring *s
s = StrCreate()
这样就可以了
