串（string）是由零个或多个字符组成的有限序列，又名叫字符串。子串在主串中的位置就是子串的第一个字符在主串中的序号。
子串的定位操作通常称做串的模式匹配。
KMP模式匹配算法
说句实话，其实我没完全搞懂这个算法，不过，还是整理一下吧。
1、字符串结构
typedef struct
{
char *ch;// 指针域，存放字符串的首地址
int len;// 整形域，说明字符串长度
}String;2、改正后的求next数组的函数
// 求模式串T的next函数修正值并存入数组nextval
void get_nextval(String T, int *nextval)
{
int i, j;
i = 1;
j = 0;
nextval[1] = 0;
while(i < T.len)
{
if(j == 0 || T.ch[i] == T.ch[j])// i表示后缀的单个字符，j表示前缀的单个字符
{
++i;
++j;
if(T.ch[i] != T.ch[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];// 若字符不相同，则j值回溯
}
}3、KMP函数
// 返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数返回值为0
// T非空，1 <= pos <= StrLength(S)
int Index_KMP(String S, String T, int pos)
{
int i = pos;
int j = 1;
int next[255];
get_nextval(T, next);
while(i <= S.len && j <= T.len)
{
if(j == 0 || S.ch[i] == T.ch[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if(j > T.len)
return i - T.len;
else
return 0;
}4、求字符串长度
// 求字符串长度
int StringLen(String S)
{
int len = 0;
while(*(S.ch++) != '\0')
len++;
return len;
}结果分析：
结果正确，但这个算法还是有问题，或许这是我的问题，构建的串的存储结构与这个算法不太相容。这个算法只能求一个由主串的后面几个字符组成的子串（且必须到尾字符）的位置，而字符串中间的字符组成的子串、从第一个字符开始的子串，它们的位置都求不出来，我也没找出问题出在哪。就像下面这样：
Index_KMP函数的返回值为0，很明显这个结果是错误的。
算法具体介绍请参考《大话数据结构》P135-P145。
