Storm-KMP
Superiority
·
·
算法·理论
$KMP$ 用于字符串匹配，先看暴力如何做每次匹配起点，如果不等，找下个；如果相等就依次看后面是否相等，但如果遇到大部分相等这种极端情况时间复杂度便会达到 $O ( m n ) $ ！
而 $KMP$ 其实是把对暴力的优化，避免多余的找起点!
我们定义一个数组 $next$，代表包含 $i$ 前面的最长重复的前缀和后缀。
现在我们要如何求解 $next$ 数组呢？我们不妨先从 $next_i$ 看起，很显然我们可以由 $next_{i-1}$ 推导过来，这时会有两种情况：
- 当 $s_{j+1} \ne s_{i}$ 也就是这两个位置不匹配的情况，我们就要往前不断搜索直到 $s_{j+1}=s_i $ 或者 $j = 0$ 这两种情况，我们要怎么往前搜呢？我们想 $next$ 的数组代表的是 包含 $i$ 前面的最长重复的前缀和后缀，如果 $s_{j+1} \ne s_i$ 的话，也就说明 $j+1$ 和 $i$ 这个时候不匹配，我们就直接暴力找到与 $i$ 匹配的，直接 `while` 查找，每次 $j$ 都要往前搜与 $i$ 匹配的，所以 $j = next_j$ 直到满足或者 $j=0$ 为止。
- 当 $s_{j+1}=s_i$ 这种情况很好想，证明 $i$ 与 $j+1$ 匹配，所以 $next_i = ++j $ ，不过需要注意的是 $j = 0$ 的时候代表无法匹配，不能给 $next_i$ 复制，要判断一下。
还有如何初始化呢？只要搞懂了定义自然迎刃而解。$next_1$ 的时候，只有自己一个字符，没有相匹配的字符，只能为 $0$。
```cpp
void KMP(){//border
nxt[1]=0;//注意初始化
for(int i=2;i<=n;i++){
while(idx&&s[i]!=s[idx+1]) idx=nxt[idx];
if(s[idx+1]==s[i]) idx++;
nxt[i]=idx;
}
}
```
~~这东西其实叫border~~
- 下面是模式字符串查找部分 ~~（但其实不常用，所以主要是border~~
现在都知道$nxt_i$（最长重复的前缀和后缀）后面其实就好做了。如果当$x_i=y_{idx+1}$时，此时它们没有失配，就可以接着往后匹配，反之失配时，则需找到没有失配的开头。
```cpp
for(int i=1;i<=len;i++){//len->模式匹配字符串的长度
while(idx&&y[idx+1]!=x[i]) idx=nxt[idx];//y->需要匹配的模式字符串
if(x[i]==y[idx+1]) idx++;//在x里查找模式字符串y
if(idx==n){
cout<<i-idx+1<<endl;
idx=nxt[idx];
}
}
```