[success]研究这个算法，着实研究了我好久，特别是kmp算法，现在都还有点蒙，不过还是可以大概理解的，这里代码部分kmp不好解释，所以我就直接上图了。[/success]
字符串匹配算法就是相当于在字符串中查找某个字符串，有两种实现算法，一个是BF算法，还有一个是KMP算法，先讲一下BF算法。
BF算法其实就是一个不断匹配的算法，S作为主串每次匹配失败后只移动一位，而T则不断从头开始继续和S进行匹配。BF算法，容易理解，下面重带讲那个难以理解的KMP算法（这里我参考了别人的博客（传送门））：
首先我们讲一下一个概念：前缀和后缀
前缀：指的是字符串的子串中从原串最前面开始的子串，如abcdef的前缀有：a,ab,abc,abcd,abcde
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcdef的后缀有：f,ef,def,cdef,bcdef
KMP算法引入了一个next数组，next[j]表示的是前j-1的字符组成的这个子串最长的相同前缀后缀的长度！
怎么理解呢？
例如字符串aababaaba的相同前缀后缀有a和aaba，那么其中最长的就是aaba。
注意：我们后面的字符串都是从1开始的，数组的第0位我们不用,所以解释上和我参考的博客是不一样的，next的值也是不一样的，请大家自行理解原理，不要死记
这里我举一个例子：
B= "a b a a b c a c"
next= 0 1 1 2 2 3 1 2
next为0就是说如果第一个都不匹配的话，那么继续匹配。如果为1，说明没有相同的最长前缀和后缀。
比如我们拿next[5]，next[6]，next[7]分别说明一下next[5]为2，说明前j-1=4个字符“abaa”中最长相同前缀和后缀是1也就是a，那么下次匹配时直接从第2位开始。next[6]为3，那么前j-1=5个字符"abaab"最大相同前缀后缀是"ab",(这里就是倒着数和顺着数（这里不是真的倒着数）前面出现的都有ab)，next[7]为1，"abaabc"说明没有相同的字符，所以B要从头开始比较。
注意：这里前缀和后缀是理解next的关键
有了这个next后，我们就可以开始匹配了（这里我贴一张别人的图片）
其实原理很简单，就是S主串每次匹配都会+1，而子串每次也是加1，只是如果不匹配的话，那么字符就会回到第next[j]位上重新进行比较，而i是不变的。
重要的是理解下面这个代码。
if (j == 0 || S.ch[i] == T.ch[j]) { ++i, ++j; }
else j = next[j];
这个是什么原理呢？
其实就是利用了前面那个相同前缀和后缀，比如我们匹配时发现有S和T不匹配，那么我们知道，S和T前面都是相同的（指的是S前面和T匹配的部分），我们可以把S看成B的后缀，那么我们可以根据next知道和B后缀相同的最长前缀是第几位，那么，B就不需要从头开始了，直接从这位开始，因为前面这几位和S是匹配的。
那么直接上代码了：
//串的存储结构
#include"pch.h"
#include <iostream>
using namespace std;
//串有3种存储结构：顺序存储，堆式顺序存储，链式存储
//顺序存储
#define MAXLEN 255 //定义串的最大长度
typedef struct
{
// 我们声明数组时需要多申明一个，目的是保留一位作为结束位
char ch[MAXLEN + 1];
int length;
}SString;
//-------串的堆式顺序存储结构
typedef struct {
//相当于这个ch*是一个指向数组首地址的指针
char *ch;
int length;
}HString;
//---串的链式存储结构
#define CHUNKSIZE 80//这里是块的大小
typedef struct Chunk
{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct
{
Chunk *head, *tail;//定义了头尾指针，分别指向头尾
int length;
}LString;
/*
这里因为时间的关系，所以我这里也不说字符串怎么添加，我们这里直接说一下
字符串匹配的算法，字符串有两种匹配的算法，一个是BF算法，一个是KMP算法
*/
int Index_BF(SString S, SString T, int pos)
{
//BF算法就是，两个串不断进行匹配，如果相等就继续向下匹配，如果不等，那么指针就要后退重新开始匹配
//这个pos就是开始匹配的位置
int i = pos, j = 1;
while (i <= S.length && j <= T.length)//两个字符串均未到达末尾
{
//这里就是如果I超了，就说明匹配失败，如果j超了就说明匹配成功
if (S.ch[i++] !=T.ch[j++]) { i = i - j + 2; j = 1; }
//上面是不断比较，如果发现有不一样的那么i就要回退i-j+2，j要回到1
//之所以是i-j+2 是相当于比较了j个字符，然后i要回退j个字符（i-j+1）在原来的基础上在加1
}
if (j > T.length) return i - T.length;//如果j>T.length说明匹配成功，那么就返回字符串的起始位置
else return 0;
}
//KMP算法的实现
//这个算法的改进在于每当一趟匹配出现不相等时，不需要回溯i指针，而是利用已得到的“部分匹配结果”，
//只需要j回退就可以继续进行匹配
//在进行KMP算法之前，我们需要先计算next的值
void get_next(SString T, int next[8])
{
int i = 1, j = 0;
next[1] = 0;
while (i < T.length)
{
//next就是计算相同前缀的长度的值
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 next[8])
{
int i = pos, j = 1;
while (i<=S.length && j<=T.length)
{
//kmp算法，就是i不断的进行+，不回溯，j则根据next的值，自己回溯
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;
}
int main()
{
SString *S = new SString;
S->length = 17;
S->ch[1] = 'a';
S->ch[2] = 'c';
S->ch[3] = 'a';
S->ch[4] = 'b';
S->ch[5] = 'a';
S->ch[6] = 'a';
S->ch[7] = 'b';
S->ch[8] = 'a';
S->ch[9] = 'a';
S->ch[10] = 'b';
S->ch[11] = 'c';
S->ch[12] = 'a';
S->ch[13] = 'c';
S->ch[14] = 'a';
S->ch[15] = 'a';
S->ch[16] = 'b';
S->ch[17] = 'c';
SString *T= new SString;
T->length = 8;
T->ch[1] = 'a';
T->ch[2] = 'b';
T->ch[3] = 'a';
T->ch[4] = 'a';
T->ch[5] = 'b';
T->ch[6] = 'c';
T->ch[7] = 'a';
T->ch[8] = 'c';
//先初始化我们的字符串,这里为了方便起见，我就不给0赋值
int i = Index_BF(*S, *T, 1);
cout <<"字符的位置在:"<<i << endl;
int next[9] ;
get_next(*T, next);
cout << Index_KMP(*S, *T, 1, next);
return 0;
}
至于这个next值是怎么计算的呢？
int i = 1, j = 0;
next[1] = 0;
while (i < T.length)
{
//next就是计算相同前缀的长度的值
if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
我们可以看到，这个i就相当于在计算后缀，而j则是充当前缀的角色。就相当于B前i位的后缀和B前j位的前缀进行比较，如果匹配就记下j（这个j其实就是最大的前缀数，因为B的前j位和i的后i位是匹配的）
好了，这个算法就解释到这里，最后还想吐槽下，这个算法还是不好理解，研究了两天才勉强看懂。
