算法通关(3) -- kmp算法

KMP算法的原理

从题目引出

有两个字符串s1和s2,判断s1字符串是否包含s2字符串，如果包含返回s1包含s2的最左开头位置，不包含返回-1，如果是按照暴力的方法去匹配，以s1的每个字符作为开头，用s2的整体去匹配，那么得到的时间复杂度达到O(m*n),若字符串长度过长，那么可能导致不能AC。。。那么可不可以利用前面的匹配过程去帮助匹配加速，某些位置不用按照一个位置一个位置的去匹配。有的，这就是今天要了解的KMP算法。

1.next数组的定义

先知道是怎么回事就行

用s2去匹配s1,next数组是对于s2来说的；含义：不包含当前，它前面字符串前缀和后缀最大匹配长度，也不能包含整体：例如前面的字符串abc，如果包含整体，abc一定匹配abc,没有了意义.

对于0位置的a来说，它的前缀什么都没有，因此放一个-1表示不存在；对于1位置的a来说，前面有一个a,但是只有一个字母，不能够进行匹配，匹配则违反了包含整体（此时整体只有一个1），因此1位置是0；对于2位置b来说，前面是aa,前缀一个a，后缀一个a，刚好匹配，因此填1；

对于3位置的a来说,前面是aab,取一个（前缀是a,后缀是b,不行），取两个（前缀是aa,后缀是ab,不行），因此是0.。。。依次类推，对于6位置的x来说，前面是aabaab,最长匹配字符串是3，因此填3；

同理：对于12位置的a来说，选择5个是最大的匹配长度。 记住，不包含当前下标的字符！！！

 2.如何加速匹配？

匹配到13位置不相同，下次位置从哪里匹配？匹配不上的next位置是6，那么让s2的6位置的c去匹配s1的13位置，也就是说，前面的1~6位置被放弃了！！！这里引出两个问题：
1：为什么放弃前面的？2：s2的0~5位置为什么不用验证，可以直接从6位置的c开始和s1的13进行匹配？

第二个问题：

先回答第二个问题：因为next数组是不包含当前，它前面字符串前缀和后缀最大匹配长度,为什么是6，因为那个位置的s2字符串前面数6个和后面数6个得到的字符串相同！！！如图：

 由于s1和s2的匹配，可知m1和n1相同，m2和n2相同，又因为next数组，n2和n1相同，那么这四个都相同，就可以得出n1和m2相同，既然相同了，那么就没必要费时间从头开始了。继续匹配如下图：

 第一个问题：

 四个红色方框长度相同.上面说的是s2从k位置开始匹配,假设可以从小于k的位置进行匹配，例如图中的m位置，因为s1的m位置之后和s2之后的字符相同（不包含j位置，因为是从哪里进行的退出），

 从m位置进行匹配可以成功，那么s1的绿色和s2的绿色（下边）一定可以匹配成功，由于s1的绿色第一次匹配时和s2的绿色（上边）匹配成功，因此可以得到s2的这两端绿色是相同的字符串

 而这个长度超过了next数组给定的长度，因为只要匹配上，next算的是不包含当前，它前面字符串前缀和后缀最大匹配长度，违背了next记录最大长度。这样子就加速了匹配的进程

3.KMP算法代码

int kmp(const string& s1, const string& s2) {
    // x是s1的比对位置
    // y是s2的比对位置
    int n = s1.length(), m = s2.length(), x = 0, y = 0;    
    // 获取next数组 
    vector<int> next = nextArray(s2, m);
    // 不越界
    while (x < n && y < m) {
        if (s1[x] == s2[y]) {
            // 每个位置可以匹配的上
            x++;
            y++;
        }
        // 当前不等
        else if (y == 0) {
            // 如果是s2的0位置没有匹配出来，无法往前跳了
            // s1换个位置开头吧，s2不动
            x++;
        }
        else {
            // s2的其他位置没有匹配出来，按照s2的y位置的next[y]跳跃
            // s1不动，s2换个位置配
            y = next[y];
        }
    }
    // s2匹配ok了,就找到了
    // 越界还没有找的，返回-1
    return y == m ? x - y : -1;
}

4.next数组如何快速生成

按照前面的next值求下一个位置的next值

情况1：不用跳

求得“？”位置的next值，看的是前面字符的最大匹配长度，得知是8；也可以看前面“x”位置的next值，是7，看他与7位置的字符是否相同，这里相同，因为不相同就必须跳了，那就+1，得到8，为什么不能够更长呢？如图：

 情况2：需要跳

用图来说吧

 如果没有对上，继续跳，如果跳到头都没有跳出来，那么要求的next就是0。

为什么这样子，其实找的前缀和后缀都是在s2这个字符串中，即在一个字符串中找到尽可能的长的前缀和后缀，这就是next数组的含义，因为要保留尽量长！！！举个例子

 5：next数组代码

vector<int> nextArray(const string& s, int m) {
    // m是字符串s2的长度
    if (m == 1) {
        return { -1 };
    }
    // next的第一个位置和第二个位置是固定的
    vector<int> next(m);
    next[0] = -1;
    next[1] = 0;
    // 从第二个位置开始填
    int i = 2, cn = 0;
    // 没有越界
    while (i < m) {
        // i 表示当前要求的next值的位置
        // cn表示当前要和一个字符比对的下标
        if (s[i - 1] == s[cn]) {
            // 后面的字符是cn位置
            // 为什么是++cn，而不是cn+1
            // 因为为了下面可能用到cn的值，如果后面的字符是cn位置，那么直接用
            // 当前位置求完了，求下一个位置就是++
            next[i++] = ++cn;
        }
        else if (cn > 0) {
            // 不一样，向前跳
            cn = next[cn];
        }
        else {
            // 已经等于0了，再往前跳到-1位置
            next[i++] = 0;
        }
    }
    // 得到next数组
    return next;
}

KMP算法相关题目

题目1：

P4391 [BOI2009] Radio Transmission 无线传输 - 洛谷 | 计算机科学教育新生态

总长度是k个最短长度(设为n)的字串加上尾巴的一些，尾巴长度为L，那么总长度为k*n+L,前缀最大的长度串是（k-1）*n+L,因为此例中是以a开头，下一个a是经过了一次循环后的a,因此可以得到最大长度串。

两个疑惑:它可以更短吗？不可以，因为next求得就是它前面字符串前缀和后缀最大匹配长度。
它可以更长吗？不可以，举个例子：
 

因此可以得出结论：不能够变得更短，也不能变得更长！！！

代码如下：

#include <iostream>
#include <vector>
#include <string>

using namespace std;
const int MAXN = 1000001;
int next_[MAXN];
int n;
string s;

void nextArray() {
    next_[0] = -1;
    next_[1] = 0;
    int i = 2, cn = 0;
    while (i <= n) {
        if (s[i - 1] == s[cn]) {
            next_[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next_[cn];
        }
        else {
            next_[i++] = 0;
        }
    }
}

int compute() {
    nextArray();
    return n - next_[n];
}

int main() {
    cin >> n;
    cin >> s;
    cout << compute() << endl;
    return 0;
}

题目2：

[USACO15FEB] Censoring S - 洛谷

利用栈，压入s1位置字符的下标以及s2位置字符的下标。
如果位置字符下标的值对应，那么两个字符向前++，当s2越界了，那么表示s1的一段和s2匹配上了，那么使栈的长度-s2的长度，然后根据栈顶元素的下标，让s2找到正确的下标。如图：

 代码如下:

#include <iostream>
#include <vector>
#include <string>

using namespace std;


const int MAXN = 1000001;
int next_[MAXN];
// 栈1压s1，栈2压s2
int stack1[MAXN];
int stack2[MAXN];
int _size;
string s1, s2;

// 生成s2的next数组
void nextArray(int m) {
    next_[0] = -1;
    next_[1] = 0;
    int i = 2, cn = 0;
    while (i < m) {
        if (s2[i - 1] == s2[cn]) {
            next_[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next_[cn];
        }
        else {
            next_[i++] = 0;
        }
    }
}

void compute() {
    _size = 0;
    int n = s1.length(), m = s2.length(), x = 0, y = 0;
    // s2的next数组
    nextArray(m);
    while (x < n) {
        if (s1[x] == s2[y]) {
            // 对应的上，s1和s2两者++
            stack1[_size] = x;
            stack2[_size] = y;
            _size++;
            x++;
            y++;
        }
        // 对应不上，而且y来到s2的开头位置
        else if (y == 0) {
            // 
            stack1[_size] = x;
            stack2[_size] = -1;
            _size++;
            x++;
        }
        // 对应不上，没来到开头位置，往前跳
        else {
            y = next_[y];
        }
        // s2遍历完了
        if (y == m) {
            // 相当于栈直接弹出了m条记录
            _size -= m;
            // 处理s2的y
            // 栈中有东西，跳到栈顶的下一个位置
            // 没有就是0下标
            y = _size > 0 ? (stack2[_size - 1] + 1) : 0;
        }
    }
}


int main() {
    cin >> s1 >> s2;
    compute();
    for (int i = 0; i < _size; i++) {
        cout << s1[stack1[i]];
    }
    cout << endl;
    return 0;
}