10、数据结果与算法 - 字符串匹配问题 KMP算法
KMP算法
前面 BF算法 中有许多重复比较
例如
在第6个位置比较失败，由于前面的字符都不相同，所以将模式串的第一个位置 和主串的第6个位置开始比较就行。像BF算法中一位一位的向后移动比较，那些都是多余的。KMP算法 就是尽量减少这些没有意义的重复比较。
KMP算法 就是为了解决这些过多的重复比较产生的。KMP的核心思想是通过一个next 数组，记录模式串中各元素位置与主串的中的元素不匹配时，对应回溯位置（也就是说主串遍历不变，子串回溯到对应位置与主串当前位置开始比较）。
next 数组推导公式
分析一下这个公式
至于别人是怎么想到这样处理的，不用过多关心，只要知道其思想和用法就行
总结：
next 回溯数组:
1、next[1] = 0;
2、j 位置的 next[j], 是前 j-1 位置 比较前缀后缀，有几位就是 几+1.
例如：前 j-1 位，下面字符串长度+1 = j
aba a 与 a 相等 是1位 next[4] = 2
abab ab 与 ab 相等 是2位 next[5] = 3
ababa aba 与 aba 相等 是3位 next[6] = 4
aaaaaa aaaaa 与 aaaaa 相等 是5位 next[7] = 6
总结：前缀不能包含最后一个元素，后缀不能包含最前面一个元素，然后比较，联系相等的有多少位就是多少。然后对应next 值就是其+1.
通过上面的公式与思想，计算出模式串的next 数组。然后遍历主串和模式串，i 标记主串位置，j 比较模式串位置。通过遍历比较只要模式串没有遍历完出现不相等的情况，i 不变，j 去next 数组中找出对应的 j = next[j]。然后继续遍历。知道主串遍历完或模式串遍历完（匹配完成）。
代码实现
#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
//#include "ctype.h"
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define MAXSIZE 100 //初始化分配空间
typedef int Status; //Status 是函数的类型，其值是函数结果状态码，如OK 等
typedef int ElemType; // ElemType 类型是根据实际情况而定，这里假设为int
typedef char String[MAXSIZE+1];//0 号单位元存放串的长度，所以申请内存的时候要在初始化空间大小下 +1
//生成一个其值等于chars 的串T
Status StrAssign(String T, char * chars){
if (strlen(chars)>MAXSIZE) {
return ERROR;
}else{
T[0] = strlen(chars);
for (int i=1; i<=T[0]; i++) {
T[i] = *(chars+i-1);
}
return OK;
}
}
//清空串
Status ClearString(String S){
S[0] = 0;//串长度置为0即可
return OK;
}
//输出字符串 T
void StrPrint(String T){
for (int i=1; i<=T[0]; i++) {
printf("%c ",T[i]);
}
printf("\n");
}
//输出Next数组值
void NextPrint(int next[],int length){
for (int i=1; i<=length; i++) {
printf("%d ",next[i]);
}
printf("\n");
}
//返回串的元素个数
int StrLength(String S){
return S[0];
}//********************* KMP算法（一） **********************
//KMP 模式匹配算法
//1、通过计算返回子串T的next 数组
//注意字符串T[0] 中是存储的字符串长度；真正的字符内容从T[1] 开始；
void get_next(String T,int *next){
int i=0;
int j=1;
next[1]=0;
//例如 abcdex
//遍历T 模式串，此时T[0]为模式串T 的长度;
while (j<T[0]) {
if (i==0 || T[i] == T[j]) {
//T[i] 表示前缀的单个字符
//T[j] 表示后缀的单个字符
next[++j] = ++i;
}else{
//i 遇到不等就回溯然后继续比较
i = next[i];
}
}
}
/*
例：
模式串: a b c a b d
j: 1 2 3 4 5 6
next: 0 1 1 1 2 3
0、 next[1] =0;
1、i=0,j=1; if i==0; ++i =1, ++j =2 next[2] =1;
2、i=1,j=2; if i!=0,a!=b; i=next[1] =0;
3、i=0,j=2; if i==0; ++i =1, ++j =3 next[3] =1;
4、i=1,j=3; if i!=0,a!=c; i=next[1] =0;
3、i=0,j=3; if i==0; ++i =1, ++j =4 next[4] =1;
2、i=1,j=4; if i!=0,a==a; ++i =2, ++j =5 next[5] =2;
3、i=2,j=5; if i!=0,b==b; ++i =3, ++j =6 next[6] =3;
*///KMP 匹配算法（1）
//返回子串T 在主串S 中第pos 个字符之后的位置，如果不存在则返回-1；
int Index_KMP(String S, String T, int pos)
{
// i 是主串当前位置的小标
// j是模式串当前位置的下标。第0位置是字符串长度，从1开始
int i = pos;
int j = 1;
int TLength = StrLength(T);
int SLength = StrLength(S);
// 定义一个空的next 数组
int *next;
next = (int *)malloc(sizeof(int)*(TLength+1));
get_next( T, next);
// 注意：T[0] 和 S[0] 存储的是字符串T 与字符串S 的长度；
// 若i 小于S 长度并且j 小于T 的长度时循环继续
while (i <= SLength && j <= TLength) {
// 如果两个字母相等 或模式串从头开始 则继续循环，j++,i++
if (j==0 || S[i] == T[j]) {
i++;
j++;
}else{
// 如果不匹配时，j回退到合适的位置，i值不变
j = next[j];
}
}
// 当模式串遍历完的时候，说明全部匹配成功
if (j > TLength) {
return i-TLength;
}else
return -1;
}优化
通过上述的KMP算法之后，还会有重复的。
例如
主串： a d c a d d a d a
模式串：a d a
next： 0 1 2
当遍历到主串第3个位置 c 的时候，不匹配，这时候 j = next[3] = 2 。这时候比较如下：
主串： a d c a d d a d a
模式串： a d a
其实呢，这时候，可以直接再往后移动一位直接c 和 a 比较。如下
主串： a d c a d d a d a
模式串： a d a
那么就需要优化一下next
总结：
也是先算next 之后，然后根据nextVal[nextVal[j]] 与当前元素比较，如果相同，就nextVal[j] = nextVal[nextVal[j]]
如果不相同就用算出来的值。
nextVal[1] =0;
KMP 思路
1、遍历模式串TS，i 是用来标记主串的索引；遍历模式串 T，j是用来标记模式串的索引；
2、结束条件是当 i > S.length 或 j > T.length;
（1）、如果i > S.length 但是j 却小于 T.length。表示主串遍历完了，模式串还没有遍历完，说明主串中没有与模式串匹配的字符串。
（2）、只有当 i<= S.length 且 j > T.length 时，也就是模式串遍历完毕均与主串中的对应字符串相匹配，说明主串中找到了模式串相匹配的字符串。
3、当j =0 时，表示此时你需要将模式串从1 这个位置与主串 i+1这个位置开始比较；
4、当 S[i] == T[j]，表示此时当前模式串j 与主串 i 这个两个字符相等。则 j++,i++;
5、当 j!= 0 并且 S[i] != T[j] 时，表示此时需要移动模式串的j，那么我们让 j = next[j];来节省重复的比较次数；
代码实现
//********************* KMP算法（一）优化 **********************
//KMP 匹配算法（2）
//求模式串 T 的next 函数值修正值并存入nextVal 数组中；
void get_nextVal(String T,int *nextVal)
{
int i=0;
int j=1;
int Tlength = StrLength(T);
nextVal[1] =0;
while (j<Tlength) {
if (i==0 || T[i] == T[j]) {
++i;
++j;
//如果当前字符与前缀不同，则当前的j 为nextVal 在i 位置的值
if (T[i] != T[j]) {
nextVal[j] = i;
}else
//如果当前字符与前缀相同，则当前前缀的nextVal 值赋值给nextVal 在i的位置
nextVal[j] = nextVal[i];
}else
i = nextVal[i];
}
}//KMP 匹配算法（2）
//返回子串T 在主串S 中第pos 个字符之后的位置，如果不存在返回-1
int Index_KMP2(String S,String T,int pos)
{
int i=pos;
int j=1;
int SLength = StrLength(S);
int TLength = StrLength(T);
// 定义一个空的next数组
int * nextVal;
nextVal = (int *)malloc(sizeof(int)*(TLength+1));
get_nextVal(T, nextVal);
// 注意：若i<= SLength 并且 j<= TLength 循环继续
while (i<=SLength && j<=TLength) {
// 如果两个字母相等 则继续遍历比较 i++,j++
if (j==0 || S[i] == T[j]) {
i++;
j++;
}else{
// 如果不匹配时，j 回退到 nextVal[j] 位置，i不变。遍历进行比较。
j = nextVal[j];
}
}
// 当j 遍历完，说明都匹配了。那么对应i-TLength 的位置就是匹配的字符串首字符的下标
if (j>TLength) {
return i-TLength;
}else
return -1;
}
main函数检验
int main(int argc, const char * argv[]) {
printf("************ KMP算法 ***************\n");
/*关于next数组的求解*/
StrAssign(s1,"abcabd");
printf("子串为: ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next为: ");
NextPrint(p,StrLength(s1));
t=(int*)malloc((i+1)*sizeof(int));
get_nextVal(s1, t);
printf("NextVal为: ");
NextPrint(t,StrLength(s1));
printf("\n");
//KMP算法调用
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcdex");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"abccabcceabc");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcce");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"aaaabcde");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"aaaaax");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP2(s1, s2, 1);
printf("主串和子串在第 %d 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
return 0;
}
************ KMP算法 ***************
子串为: a b c a b d
Next为: 0 1 1 1 2 3
NextVal为: 0 1 1 0 1 3
主串为: a b c a b a b c a
子串为: a b c d e x
主串和子串在第 -1 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第 -1 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
主串为: a b c c a b c c e a b c
子串为: a b c c e
主串和子串在第 5 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第 5 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
主串为: a a a a b c d e
子串为: a a a a a x
主串和子串在第 -1 个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第 -1 个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]