KMP初步

佚名 6年前 (2019-04-10) 随笔 342人围观抢沙发百度已收录

KMP算法

介绍

用处：用于串的模式匹配，即找出模式串在主串中的出现位置

朴素想法，直接遍历两个串，失配回到主串开始比较位置的下一位继续匹配，复杂度$O(nm)$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

KMP算法即在$O(n+m)$复杂度内匹配的算法

算法实现

通过一个叫$next$数组的东西，使指向主串的$i$指针不回溯，只改变指向模式串的$j$指针

所以重点就是在于失配后$j$移动到哪里，也就是关于$next$数组的部分

$Next[]$的基本意义：

在串ss中寻找串s，

当前已经得到了$s[1…j-1]=ss[i-j+1…i-1]$，

正在检查$s[j]与ss[i]$是否相等，发现不相同，失配，

（如果相同，i和j自增1，继续向后检查）

如果按照暴力算法，ss上的“指针”需要回到i-j+1，s上的“指针”j需要回到0；

我们试图让i往回不移动，仅仅是让j往回移动，移动到一个合适的、不会丢失任何匹配可能的位置，这个位置就是我们的Next[j]。

$next$数组的定义是

即最大的$P[1 , k-1] = P[j-k+1 ,j-1]$

求出next之后在失配时让$j=next[j]$就是KMP算法了

如何求出$next$

已知 Next[j]=kn。

即存在 $s[1,kn-1]=s[j-kn+1,j-1]$

（最长后缀等于字符串前缀）

分情况讨论，对于$j+1$（现在需要求的Next数组位）有两种情况

若$ s[kn]=s[j]$，那么可以得到 $s[1,kn]=s[j-kn+1,j]$ ，根据定义，不难推断出$Next[j+1]=kn+1$
若不相等，则转化为匹配自身的问题，不断地令$j=Next[j]$直至出现 $s[kn]=s[j]$（转化为1情况，$Next[j+1]=kn+1$）；或者$j=1$（找不到后缀等于前缀）匹配到头，$Next[j+1]=1$。

模版

#include <bits/stdc++.h>
#define N 1000005
using namespace std;

int n, m;

int nxt[N];
int s[N], t[N];

void getNext(int t[]) {
    int i = 1, j = 0;
    nxt[1] = 0;
    while (i < m) {
        if (j == 0 || t[i] == t[j]) {
            i++; j++;
            nxt[i] = j;
        }
        else j = nxt[j];
    }
}

int kmp(int s[], int t[], int pos) {
    int i = pos, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || s[i] == t[j]) {
            i++; j++;
        }
        else j = nxt[j];
    }
    if (j > m) return i - m;
    else return -1;
}

int main() {
    int t1;
    scanf("%d", &t1);
    while (t1--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d", &t[i]);
        }
        memset(nxt, 0, sizeof(nxt));
        getNext(t);
        printf("%d\n", kmp(s, t, 1));
    }
    return 0;
}