## KMP (Knuth-Morris-Pratt 算法)
> 快速模式匹配算法，实现线性时间的字符串匹配
### 功能
用 `pat` 表示模式串，长度为 `M`，`txt` 表示文本串，长度为 `N`。
KMP 算法是在 `txt` 中查找子串 `pat`，如果存在，返回这个子串的起始索引，否则返回 -1。
### 性能
| | 时间复杂度 | 空间复杂度 |
| -------- | ---------- | ---------- |
| 暴力匹配 | O(m*n) | O(1) |
| KMP | O(m+n) | O(m) |
### 原理
暴力匹配会不断回退，重复搜索
```c++
// 暴力匹配（伪码）
int search(String pat, String txt) {
int M = pat.length;
int N = txt.length;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (pat[j] != txt[i+j])
break;
}
// pat 全都匹配了
if (j == M) return i;
}
// txt 中不存在 pat 子串
return -1;
}
```
KMP只遍历`txt` 一次，不回退。
1. 计算next数组
next[i]的值可视为`pat`在前i位最长相同前后缀的长度。
2. 根据next数组进行匹配
### 代码实现
```c
void get_next( String pat,int *next)
{
int i=1,j=0,len;
next[1]=0;
len=pat[0] - '0';
while( i < len)
{
if(0 == j || pat[i] == pat[j])
{
i++;
j++;
next[i]=j;
/*if( T[i]!=T[j]) //优化
{
next[i]=j;
}
else
{
next[i]=next[j];
}*/
}
else
{
j=next[j]; //要回溯到next[j]位置
}
}
}
```
```c++
int Index_KMP(string txt, string pat, int pos)
{
int i=pos,j=1;
int next[255];
int txtLen,patLen;
get_next(pat,next);
txtLen=txt[0]-'0';
patLen=pat[0]-'0';
while( i <= txtLen && j <= patLen) //其中一个字符串达到末尾则终止匹配过程
{
if( 0==j || txt[i] == pat[j] )
{
i++;
j++;
}
else
{
j=next[j];
}
}
if( j > patLen )
{
return i-patLen;
}
else
{
return -1;
}
}
```
调用
```c++
int main(){
string S="5abcdex";
string T="2cd";
int pos=Index_KMP(S,T,0);
printf("%d\n",pos);
return 0;
}
```
## 参考
[最浅显易懂的 KMP 算法讲解](https://www.bilibili.com/video/BV1AY4y157yL?spm_id_from=444.41.list.card_archive.click)
[KMP 算法详解](https://zhuanlan.zhihu.com/p/83334559)
[c实现](https://blog.csdn.net/dayuhaitang1/article/details/115361304)
KMP (Knuth-Morris-Pratt 算法)
