串这个概念对于我们学到现在的水平来说应该是经历颇丰了，因为在C语言中我们所用到的“串”知识是在字符串那里，有了这个概念，我们再去学习串就相对而言轻松多了。
那么，现在来介绍一下字符串的基本知识点吧：
首先，所谓的串：
1.都由ASCII码组成；
2.长度基本没有要求
串的表示方式：
1.顺序存储结构——数组
2.非线性存储结构——链表
那么，我们在C语言中对于串的处理，一般无非是以下几种：
1.初始化“串”；
2.销毁“串”；
3.获取“串”长度；
4.插入单字符；
5.删除单字符；
6.定位单字符；
7.更改单字符；
8.取子串；
9.分割单字符；
10.合并单字符；
11.串匹配；
12.替换
这里和我们之前博文中对于 链表 和 表达式 的处理思想近乎相同，这里就不进行枯燥的复述了
那么，在这篇博文中，本人主要讲解一个算法来解决字符串匹配问题——KMP算法
首先，本人来解释一下什么是字符串匹配问题：
字符串匹配问题：
在一个源字符串中，查找一个目标字符串（子字符串）的第一次出现位置。
本人现在这里来阐释一下算法的基本思想：
根据给出的字串，得到一个数组，来储存当子串中的每一个元素的适配个数，然后根据这个数组中的值，遍历并比较源串和子串，当遇到不匹配的位置，读取该位置的适配字符数，将该数作为再次比较时源串的开始下表下标，因为我们这些。
那么，什么是适配呢？
适配就是指：与该字符紧挨着的前缀的字符串的部分长度，与从该字符串刚开始开始比较，长度相等、内容也完全相等的长度。
假设现在有一个字符串：
annbcdanacadsannannabnna
现在要求查找如下字串：
annacanna
那么，本人根据子串的信息来得出一个数组：
| 下标 | 字符 | 适配字符数 | 适配串 |
|---|---|---|---|
| 0 | a | 0 | |
| 1 | n | 0 | |
| 2 | n | 0 | |
| 3 | a | 0 | |
| 4 | c | 1 | a |
| 5 | a | 0 | |
| 6 | n | 0 | |
| 7 | n | 1 | a |
| 8 | a | 0 |
next[] = {0, 0, 0, 0, 1, 0, 0. 0}
这个例子其实算是比较简单的，还不能完全体现我们要初始化这个数组的原理，现在本人来给出一个比较复杂的例子：
源串：aabaabaabaabaabaaaabaabaab
子串：aabaabaaaabaa
那么，本人根据子串的信息来得出一个数组：
| 下标 | 字符 | 适配字符数 | 适配串 |
|---|---|---|---|
| 0 | a | 0 | |
| 1 | a | 0 | |
| 2 | b | 1 | a |
| 3 | a | 0 | |
| 4 | a | 1 | a |
| 5 | b | 2 | aa |
| 6 | a | 3 | aab |
| 7 | a | 4 | aaba |
| 8 | a | 5 | aabaa |
| 9 | a | 2 | aa |
| 10 | b | 2 | aa |
| 11 | a | 3 | aab |
| 12 | a | 4 | aaba |
next[] = {0, 0, 1, 0, 1, 2, 3, 4, 5, 2, 2, 3, 4}
现在，本人来通过两张图来展示下这个数组的作用：
没错，这个数组就是当子串和源串相比失配时应该移动的长度。
那么，了解了上述的算法的大致流程，我们现在就来用代码来实现一下：
首先，还是先来编写本人一贯的头文件：
mec.h:
#ifndef _MEC_H_
#define _MEC_H_
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1
#endif
KMPSearch.c:
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "mec.h"
void getNext(const char *str, int *next);
int KMPMatch(const char *str, const char *sub);
/*通过KMP算法查找字串位置 函数*/
int KMPMatch(const char *str, const char *sub) { //因为我们只是要查找位置，所以不能对 源串 以及 子串 进行更改
int *next;
int strLen; //用于存储 源串 长度
int subLen; //用于存储 子串 长度
int i = 0;
int j = 0;
if (NULL == str || NULL == sub
|| (subLen = strlen(sub)) > (strLen = strlen(str))) {
return NOT_FOUND;
}
next = (int *) calloc(sizeof(int), subLen); //我们将next数组的长度定为字串长度为了之后直接跳过不会适配的长度
getNext(sub, next);
while (str[i] && sub[j]) {
if (str[i] != sub[j]) {
if (j == 0) {
++i;
} else {
j = next[j];
//因为目标串失配点的前面的部分适配子串 和 目标串开头的部分子串内容是一样的，所以不用考虑开头那部分子串
//所以我们跳过比较这段字符串，从后面的子串开始比较，
}
} else {
++i;
++j;
}
if (sub[j] == 0) { //当我们比较到字串的下标为j时，发现子串被遍历完了，也就意味着这时子串在源串中的位置找到了
free(next);
return i - j; //因为字串长度是j，所以子串的第一个字符在源串中所对应的下标应改为当前下标（即i）- j
}
}
free(next);
return NOT_FOUND;
}
/*产生适配数组 函数*/
void getNext(const char *str, int *next) {
int i = 2;
int j = 0;
boolean isSame;
if (strlen(str) < 3) { //因为我们之后从源串的第三个单元找起，所以长度不能小于3
return;
}
while (str[i]) { //遍历 源串，查找适配点
isSame = str[i-1] == str[j];
if (isSame || j == 0) {
next[i++] = !isSame ? 0 : ++j;
} else {
j = next[j];
}
}
}
int main() {
char str[80];
char sub[80];
int index;
printf("请输入源串:");
gets(str);
printf("请输入子串:");
gets(sub);
index = KMPMatch(str, sub);
if (NOT_FOUND == index) {
printf("未找到！\n");
} else {
printf("在第%d个位置！\n", index+1); //因为数组的下标是从0开始，所以我们在表示时，要给 下标+1
}
return 0;
}
下面，我们来看一下运行结果:
可以看到，查找结果是正确的！
那么，现在本人再给出一对不存在包含关系的源串与子串，让我们再来看看查找结果：
我们能够清晰地看到，运行结果都是正确的！