KMP

#include <stdio.h>
#include "String.h"

#define MaxSize 100

void getNext(SqString t, int next[])
{
	int j,k;
	j = 0; 
	k = -1;
	next[0] = -1;
	while(j<t.len-1)
	{
		if( k == -1 || t.ch[j] == t.ch[k])
		{
			j++;
			k++;
			next[j] = k;
			if(t.ch[j] != t.ch[k])
				next[j] = k;
			else
				next[j] = next[k];
		}
		else
			k = next[k];
	}
	for(int i=0;i<MaxSize;i++)
		printf("%d ",next[i]);

}

int KMPIndex(SqString s, SqString t)
{
	int i =0,j = 0;
	int v;
	int next[MaxSize];
	for(int m=0;m<MaxSize;m++)
		next[m] = 0;
	getNext(t,next);
	while(i<s.len && j<t.len)
	{
		if(j == -1 || s.ch[i] == t.ch[j])
		{
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if(j >= t.len) 
		v = i - t.len;
	else
		v = -1;
	return v;
}

int main(void)
{
	SqString s,t;
	char s_ch[] = "cdddcdc";
	char t_ch[] = "cdc";
	StrAssign(s,s_ch); //将字符数组赋给串时，可由'\0'来判断结尾
	StrAssign(t,t_ch);
	printf("%d",s.len);
	printf("%d",KMPIndex(s,t));
	return 0;
}