KMP算法

#include <stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct {
char ch[MAXSIZE];
int length;
} sstring;

void get_next(sstring T,int next[])
{
int i=1;
next[1]=0;
int j=0;
while (i<T.length)
{
if (j==0||T.ch[i]==T.ch[j])
{
++i;
++j;
next[i]=j;
}
else
{
j=next[j];
}
}
}
int index_KMP(sstring S,sstring t,int pos)
{
int i=pos;
int j=1;
int next[MAXSIZE];
get_next(t,next);
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;
}
}
void str_to_sstring(const char* str, sstring* s)
{
int len = 0;
while (str[len] != '\\0')
{
len++;
s->ch[len] = str[len-1];
}
s->length = len;
}

int main()
{
sstring S, t;
// 存入主串和模式串
str_to_sstring("ababcabcacbab", &S);
str_to_sstring("abcac", &t);

int pos = index_KMP(S, t, 1);
if(pos)
{
printf("匹配位置：%d\\n", pos);
}
else
{
printf("匹配失败\\n");
}
system("pause");

return 0;
}