思路

【主串】ABABCABCACBAB
【模式串】ABCAC
【问题】如何在主串中找到模式串的位置？

（1）方法一：暴力
你能想到的，而且最简单的方法就是：用两层循环遍历两个串，直到完全相同，则返回位置（详细看本文内容：1 【方法一代码】暴力搜索）

思考

方法一当然是最简单最暴力，但是最不省力最不省时间
但如果你自己运行几个例子，就会发现方法一中有非常非常多不必要的回溯！但是你又说不明道不清
而KMP就帮你归纳出了很多不必要回溯的情况（详细看本文内容：2 哪些是不必要的回溯？）

（2）方法二：KMP算法
避免不必要的回溯：主串指针i不回溯，模式串指针j只往前回溯一点。这非常nice，可以减少很多工作量

KMP这么牛？那它是怎么避免没有必要的回溯？
详细看：3 KMP怎么避免没有必要的回溯（NEXT数组）
NEXT数组怎么算？
避免回溯的核心是NEXT数组？那它是怎么算的？（详细看：4 如何求next数组？）
KMP是怎么工作的？
有了NEXT数组以后，我们的匹配工作应该怎么来操作？（详细看本文5 KMP完整代码）
KMP算法的改进
KMP算法已经很牛了，还有改进的地方？没错，在这个思路中还有一些不必要的回溯，你可能都没有发现。KMP算法的改进即是修改next数组，再一次避免了不必要的回溯（详见本文内容：7 next数组的改进（nextval数组））

方法一代码暴力搜索

主串指针i回溯到刚才的下一个位置

模式串指针j回溯到0

// 下标为0的位置存储的是字符串长度
int bf(char *s, char *p)
{
  int i=0; //遍历s
  int j=0; //遍历p
  while (i<=s[0] && j<=p[0])
  {
      if (s[i]==p[j])
      {
          ++i;
          ++j;
      }
      else //失配
      {
          i=i-j+2; //i回溯到原来的下一个
          j=0;
      }
  }
  if (j>p[0]) //匹配成功
  {
      return i-j+1;
  }
  else return 0;
}

2 哪些是没有必要的回溯？

KMP的核心就是避免不必要的回溯。
【四个思考例子】什么是没有必要的回溯？

【第一个】子串中没有重复的元素
- 【当前情况】i=5，j=5时发生不匹配
- 【暴力算法】那下一步，i就要回溯2，j要回溯到1（i=2，j=1）
- 【思考】试一下发现完全没有必要回溯到这么多直接i5与j1对齐进行下一次匹配 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 14 | I | L | O | V | E | F | I | S | H | C | . | C | O | M | | 模式串T | 5 | I | L | O | V | X | | | | | | | | | |

【第二个】子串中有重复的元素
- 【当前情况】i=3，j=3时不匹配
- 【如果是暴力算法】那下一步，i要回溯到2，j要回溯到1
- 【思考】试一下发现也存在一些必要的回溯我们可以直接让i不回溯，j回溯到2（i3与j2对齐匹配） | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 13 | w | w | w | . | F | i | s | h | c | . | c | o | m | | 模式串T | 3 | w | w | . | | | | | | | | | | |

【第三个】子串中有多个重复的元素
- 【当前情况】i6与j6不匹配
- 【如果是暴力算法】那下一步，i要回溯到2，j要回溯到1
- 【思考】试一下发现也存在一些必要的回溯。我们可以直接让i不回溯，j回溯到3 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 13 | b | b | s | b | b | s | . | F | i | s | h | C | | 模式串T | 6 | b | b | s | b | b | c | | | | | | |

【第四个】与上面相同，我们直接i8与s4匹配 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 7 | s | s | s | s | s | s | x | | | 模式串T | 5 | s | s | s | s | s | b | | |

【综上】

模式串的字符没有重复，j直接回溯到1
有重复，要考虑重复的地方是否能匹配，不要遗漏了

3 KMP怎么避免这些必要的回溯？（理解NEXT数组）

【KMP怎么避免不必要的回溯呢？】

【主串指针i】在匹配过程中不回溯，一条道走到黑
【至于模式串指针j】KMP中定义了一个next数组，它的作用是在两个串失配后，指导模式串指针j下一步应该去哪里

【四个思考例子】下面详细看一下next的奇妙

【第一个】子串中没有重复的元素
- 如果j位置不匹配，那么j下一个值为next[j]
- 例子：假如j=5处发生不匹配，则j回溯到1
- 例子：假如j=4处发生不匹配，则j回溯到1 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 14 | I | L | O | V | E | F | I | S | H | C | . | C | O | M | | 模式串T | 5 | I | L | O | V | X | | | | | | | | | | | NEXT数组 | | 0 | 1 | 1 | 1 | 1 | | | | | | | | | |

【第二个】子串中有重复的元素 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 13 | w | w | w | . | F | i | s | h | c | . | c | o | m | | 模式串T | 3 | w | w | . | | | | | | | | | | | | next数组 | | 0 | 1 | 2 | | | | | | | | | | |

【第三个】子串中有多个重复的元素 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 13 | b | b | s | b | b | s | . | F | i | s | h | C | | 模式串T | 6 | b | b | s | b | b | c | | | | | | | | next数组 | | 0 | 1 | 2 | 1 | 2 | 3 | | | | | | |

【第四个】 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 主串S | 7 | s | s | s | s | s | s | x | | | 模式串T | 5 | s | s | s | s | s | b | | | | next数组 | | 0 | 1 | 2 | 3 | 4 | | | |

【综上四个例子】next数组的值受模式串决定，并不直接由目标串决定！所以求next数组看其本身就可以了

4 如何求next数组

约定：字符串从下标为1的位置开始存储，下标为0的位置存放字符串的长度

4.1 手算

【举例】模式串：ABABABB

数组下标	0	1	2	3	4	5	6	7
模式串	7	A	B	A	B	A	B	B
NEXT数组		0	1	1	2	3	4	5

【NEXT求法】在发生不匹配时，NEXT数组指导模式串指针j下一步去哪（即next[j]的位置）

j（当j=？时，发现不匹配）	F（j前面的子串F）	F前后重合部分	重合部分的长度	next[j]取值（F中前后重合字符串的长度+1）
1	``（F为空）			0（此属第一种特殊情况）
2	`A`	无（不存在前后重合部分）		1（此属第二种特殊情况）
3	`AB`	无（不存在前后重合部分）		1（此属第二种特殊情况）
4	`ABA`	`A`	1	2（长度+1）
5	`ABAB`	`AB`	2	3（长度+1）
6	`ABABA`	第一种：`ABA` 第二种：`AB`	3（取长的重合部分，即`ABA`）	4（长度+1）
7	`ABABAB`	`ABAB`	4	5（长度+1）

【总结】

【手算步骤】
- 遍历模式串，记下j前面的子串F
- 看F是否有重复出现的前后缀
  - 字符串F为空 —> 第一种特殊情况—> next[j]=0
  - 没有重复的前后缀 —> 第二种特殊情况 —> next[j]=1
  - 有一个重复的前后缀 —> 记下长度len —> next[j]=len+1
  - 有多个重复的前后缀 —> 取最长的那个，记下长度len —> next[j]=len+1
【第一种特殊情况】模式串中的第一个字符（j=1时）发生不匹配，应从 主串指针i的下一个位置 和 模式串的第一个位置 继续比较
【第二种特殊情况】当串F（模式串指针j前面的子串F）不存在前后重合的部分（自身重合不算！），则从 主串发生不匹配的字符 和 模式串第一个字符 开始比较

【把手算的思路实现成代码】此方法写成代码，太麻烦，有没有更容易的方法？

遍历数组，获得指针前的子串F
为子串F设置前后两个指针，位移判断出两个最长的共同部分

4.2 代码

【思考】手算的方法太过麻烦，有没有更简单的方法？
在手算时，next数组是从左到右计算出来的。也就是说我们在求next[j]时，next[j-1]已经知道了
那么，我们可以把 “求next数组的问题” 简化成 “已知next[j]，求next[j+1]的问题”（包含的思想：把之前的工作的结果合理利用起来，减少重复劳动！）
【问题】已知next[j]值为t，求next[j+1]
【临界情况】next[1]=0
【求法】此时，应该是T[j]与T[t]比较（T[j]为后缀的最后一个，T[t]为前缀的最后一个）

【若】T[j]==T[t]，【那么】next[j+1]=next[j]+1，即next[j+1]=t+1
- 【为什么？】next[j+1]与next[j]相比，重复的前后缀多了T[j]这一个字符
【若】T[j]!=T[t]，即j、t位置失配，【那么】t应该回溯到next[t]
- 如果这时候t为0了 —> 前面已经没有重复的前后缀了，那么next[j+1]=1（回到模式串第一个字符的位置）

【代码实现】

// T[0]存着字符串的长度
void getnext(char *T, int next[])
{
    int j=1, t=0;
    next[1]=0; //临界状态
    while (j<T[0]) //已知next[j]，求next[j+1] --> 所以j!=T[0]
    {
        if (t==0) //t=0，即回溯到了模式串的最前面
        {
            next[j+1] = t+1; //此时，next[j+1]=1，也可写成next[j+1]=t+1
            ++j;
            ++t;
        }
        if (T[j]==T[t]) //匹配成功：next[j+1]相对于next[j]讲，重复的前后缀多了一个字符T[t]
        {
            next[j+1] = t+1;
            ++j;
            ++t;
        }
        else //失配，t回溯到next[t]的位置
        {
            t = next[t];
        }
    }
}

【发现有一个地方可以合并】

// T[0]存着字符串长度
void getnext(char *T, int next[])
{
    int j=1,t=0;
    next[1] = 0; //特殊状态
    while (j<T[0]) //已知next[j]求next[j+1]，所以j不能等于T[0]
    {
        if (t==0 || T[j]==T[t])
        {
            next[j+1] = t+1;
            ++j;++t;
        }
        else
            t = next[t];
    }
}

5 KMP完整代码

【KMP怎么用】

根据模式串计算出next数组
主串的i位，模式串的j位匹配失败
- i不回溯
- j回溯到next[j]的位置

约定：字符串从下标1开始存储，下标0为字符串长度

// T[0]存着字符串长度
void getnext(char *T, int next[])
{
    int j=1,t=0;
    next[1] = 0; //特殊状态
    while (j<T[0]) //已知next[j]求next[j+1]，所以j不能等于T[0]
    {
        if (t==0 || T[j]==T[t])
        {
            next[j+1] = t+1;
            ++j;++t;
        }
        else
            t = next[t];
    }
}
// KMP搜索：下标0处存长度
int KMP(char *str, char *substr, int next[])
{
    int i=1,j=1;
    while (i<=str[0] && j<=substr[0])
    {
        if (j==0 || str[i]==substr[j])
        {
            ++i;++j;
        }
        else //失配，回溯
        {
            j = next[j];
        }
    }
    if (j>substr[0]) //匹配成功
        return i-substr[0];
    else:
        return 0;
}

6 总结

名称	思路	评价
BF简单模式匹配	暴力：遍历两个串，相等位移，直到完全一样	O(M*N)
KMP算法	主串指针i不回溯子串指针j回溯受next[j]指导	O(m+n)

【KMP方法的优点】

避免了大量不必要的回溯
大文本匹配时，不需要将主串全部读取，可分批读入进行匹配，减少存储空间和I/O操作，提高效率
- 【解释】主串指针i不需要回溯 —> 意味着对于规模较大的外存中字符串的匹配操作可以分段进行，先读入内存一部分进行匹配，完成之后即可写回外存，确保在发生不匹配时不需要将之前写回外存的部分再次读入，减少了I/O操作，提高了效率

【字符串模式匹配其他方法汇总】https://blog.csdn.net/summer_dew/article/details/78088468

7 next数组的改进（nextval数组）

【前言】有人发现KMP中还有一些没有必要的回溯
【KMP中存在的不必要的回溯】举一个比较极端的例子，你就能发现KMP中不必要的回溯

【匹配进行到i=5,j=5的情况，此时S[5]='C'和T[5]='A'失配】j退回到next[j]，即j=4；i还是为5
【S[5]='C'和T[4]='A'仍然失配】j退到next[j]，即j=3；i还是为5
【继续下去】j一直退到0
【j=0】执行i++,j++

【发现】模式串T在1-5位置上都相等，一旦5失配，其实1-4都是失配的，这时候就没有必要一步一步回溯了，直接让5回溯到0，就可避免上面的情况。即看表中的nextval
【改进】这里的nextval数组，即是我们将next数组进行了一个改进，规避了我们所举的极端情况

下标	0	1	2	3	4	5	6	7	8
主串S	8	A	A	A	A	C	A	A	A
模式串T	5	A	A	A	A	A	B
next数组		0	1	2	3	4	5
nextval数组						0

7.1 由next数组得到nextval数组（适合手算）

下标	0	1	2	3	4	5	6	7
模式串T	7	A	B	A	B	A	A	B
next数组		0	1	1	2	3	4	2
nextval数组		0	1	0	1	0	4	1

用j遍历数组下标

【特殊情况】nextval[1]=0
【看是不是特殊情况】把next[j]记为t，比较T[j]和T[t]（T[t]即T[ next[j] ]）
- 【不相等】那就不是特殊情况，next不改进，就等于原来的值：nextval[j]=next[j]=t
- 【相等】特殊情况，next需要改进：nextval[j]=nextval[ next[j] ] = nextval[t] | j | T[j] | T[ next[j] ] | nextval[j] | | —- | —- | —- | —- | | 1 | | | 特殊情况nextval[1]=0 | | 2 | T[2]=B | T[ next[2] ] =A | nextval[2]=next[2]=1 | | 3 | T[3]=A | T[ next[3] ] = T[1] = A | nextval[2]= nextval[ next[3] ]=0 |

7.2 在求next数组的过程中，一起求nextval数组（代码）

【思路】在求next数组的算法中修改部分逻辑，即可求nextval数组

// 在求next数组的过程中，求nextval数组
void getnextval(char *T, int next[], int nextval[])
{
    int j=1, t=0;
    next[1] = 0;
    nextval[1]=0; //特殊情况
    while (j<T[0]) //已知next[j]，求得next[j+1] --> 再依据next[j+1]，求得nextval[j+1]
    {
        if (t==0 || T[j]==T[t]) //匹配成功
        {
            next[j+1] = t+1; //求得next[j+1]
            // 求nextval[j+1]
            if ( T[j+1] != T[ next[j+1] ] ) nextval[j+1] = next[j+1];
            else nextval[j+1] = nextval[ next[j+1] ];
            ++j;++t;
        }
        else t = nextval[t];
    }
}

7.3 由模式串直接求得nextval数组（代码）

【求nextval的代码】不需要提前算出next数组，直接求nextval数组
已知nextval[j]的值为t，求nextval[j+1]

// 由模式串T求nextval数组
void getnextval(char *T, int nextval[])
{
    int j=1, t=0;
    nextval[1] = 0; //初始情况
    while (j < T[0]) //已知nextval[j]，求next[j+1]
    {
        if (t==0 || T[j]==T[t])
        {
            if (T[j+1]!=T[t+1]) nextval[j+1] = t+1;
            else nextval[j+1] = nextval[t+1];
            ++j; ++t;
        }
        else t = nextval[t];
    }
}

KMP

思路

方法一代码 暴力搜索