### 写在前面
关于串，906的考纲内并没有涉及，408中也只提到了模式匹配算法（KMP算法），因此这块的内容会很少，并不会有太多涉及。
一如既往的，上一部分的地址：[数据结构（2）—— 栈与队列](https://www.cnblogs.com/wushenjiang/p/15004139.html)。
### KMP匹配算法
#### 注意点
需要注意的是，代码里求next数组的过程与我们手算的过程是不一样的，因此这里的思路仅做参考。
求next数组的算法流程，可以去看王道书和[KMP算法(快速模式匹配算法)详解以及C语言实现 (biancheng.net)](http://data.biancheng.net/view/13.html)这个网址的讲解，讲的很不错。以我的能力无法叙述很好，就在此借助网络的力量了。
关于手算next数组，可以参考王道2022考研的视频，讲解的很好。
这里的代码使用了C++中定义好的string类型，并且把整体写法偏向了C++风格（实际上也就是多了个namespace的声明和打印方式的改变而已）。
#### 代码
```cpp
/*
* @Description: KMP算法实现
* @version: 1.0
* @Author: Liuge
* @Date: 2021-07-13 21:20:30
*/
#include<bits/stdc++.h>
using namespace std;
// 求next数组
// 这里的字符串是从0开始存储的，所以需要下标-1
void getNext(string T,int next[]){
int i=1;
int j=0;
next[1] = 0;
while(i < T.length()){
if(j == 0 || T[i-1] == T[j-1]){
++i;
++j;
next[i] = j;
}else{
j = next[j];
}
}
}
// KMP算法
int indexKMP(string S,string T,int next[]){
int i=1;
int j=1;
while(i <= S.length() && j <= T.length()){
if(j == 0 || S[i-1] == T[j-1]){
++i;
++j;
}else{
j = next[j];
}
}
if(j > T.length()){
return i - T.length();
}else{
return 0;
}
}
// 主函数测试
int main(){
string a = "ababcabcacbab";
string b = "cabca";
int next[100];
getNext(b,next);
cout << "子串b在子串a的起始位置为:" << indexKMP(a,b,next);
}
总结
这次实现并不是很难，而且由于考纲的要求比较低，且对代码也没什么要求，读者凑合看看就好。按照王道书上所说，暴力循环来模式匹配的方式时间复杂度其实也没那么不堪，因此也被广泛使用。在实际的项目中更多的是使用别人写好的工具类，可以参考下真正的工程项目是如何实现模式匹配的。