The Wall
0%

KMP Algorithm

发表于 更新于 Disqus：

注0：本文是在OI.Wiki-前缀函数与KMP算法的基础上写成的，二者有诸多相似。

注1：本文一切下标遵循从’0’开始的原则。

问题背景

现有文本串$t$与模式串$p$，要求用尽可能小的时间复杂度找到并输出$p$在$t$出现的所有位置。

解决此问题的关键在于前缀函数。

前缀函数$\pi[i]$

前缀、后缀、真前缀与真后缀等概念见OI.Wiki-String基础。

对于字符串$s[0\dots n],$其前缀函数$\pi[i]$定义为：

计算前缀函数

容易得到$O(n^3)$的朴素方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> getPi(string s)
{
    int length = (int)s.length();
    vector<int> pi(length);
    for (int i = 1; i < length; i++)
    {
        for (int j = i; j >= 0; j--)
        {
            if (s.substr(0, j) == s.substr(i - j + 1, j))
            {
                pi[i] = j;
                break;
            }
        }
    }
    return pi;
}

string substr (size_t pos = 0, size_t len = npos) const;

接下来在此基础上进行优化。

优化

注意到,$\pi[i+1]$至多比$\pi[i]$大1。即i++时，最好的情况是$s[i+1]=s[\pi[i]]\rightarrow\pi[i+1]=\pi[i]+1$。

由此得到$-\pi[i]\leqslant\pi[i+1]-\pi[i]\leqslant1$。

优化后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> getPi(string s)
{
    int length = (int)s.length();
    vector<int> pi(length);
    for (int i = 1; i < length; i++)
    {
        for (int j = pi[i - 1] + 1; j >= 0; j--)
        {
            if (s.substr(0, j) == s.substr(i - j + 1, j))
            {
                pi[i] = j;
                break;
            }
        }
    }
    return pi;
}

通过令$j_{i}=\pi[i-1]+1$，我们优化了比较次数。

讨论过$\pi[i+1]=\pi[i]+1$的最好情况：$s[\pi[i]]=s[i+1]$后，现在讨论$s[\pi[i]]\neq s[i+1]$的情况下，如何优化j的跳转。

失配时，我们希望找到对于子串$s[0\dots i]$仅次于$\pi[i]$的第二长度$k$，使得$s[0\dots k-1]=s[i-k+1\dots i]$，即使得在位置$i$处的前缀性质仍然得以保持。

当找到这样的$k$后，我们只需比较$s[k]$与$s[i+1]$，若$s[k]=s[i+1]$，则$\pi[i+1]=k$，否则我们需要找到仅次于$k$的第二长度$k^{(2)}$，$k^{(2)}$使得位置$i$处的前缀性质仍然保持。如此重复迭代，直到$k=0$。若$s[0]\neq s[i+1],\space\pi[i+1]=0$。

观察到，因为对任意的i，都有$s[0\dots \pi[i]-1]=s[i-\pi[i]+1\dots i]$，因此对于$s[0\dots i]$的第二长度$k$有

即，由于$s[0\dots k-1]$与长度为$i$的子串串末$k$位匹配，而$s[0\dots \pi[i]-1]$与长度为$i$的子串串末$\pi[i]$位匹配，又有$k<\pi[i]$，所以$s[0\dots k-1]$与串$s[0\dots \pi[i]-1]$的末$k$位匹配。在此情况下，$k$就是长度为$\pi[i]$的子串的前缀函数值。即$\pi[\pi[i]-1]=k$（注意下标从0开始）。

同理可得，仅次于$k$的第二长度$k^{(2)}$等于串$s[0\dots k-1]$的前缀函数值，$k^{(2)}=\pi[k-1]$。

由此我们推出了关于$k^{(n)}$的状态转移方程：$k^{(n)}=\pi[k^{(n-1)}-1],k^{(n-1)}>0$。

最终，依靠状态转移方程我们可以优化代码中j的跳转。最终得到的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> getPi(string s)
{
    int length = (int)s.length();
    vector<int> pi(length);
    for (int i = 1; i < length; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[j] != s[i + 1]) //若s[j]!=s[i+1]，通过状态转移方程找到下一个第二长度
        {
            j = pi[j - 1];
        }
        if (s[j] == s[i + 1])
        {
            j++; //若s[j]==s[i+1]，长度为i的子串的前缀函数为j+1
        }
        pi[i] = j;
    }
    return pi;
}

至此，我们得到了只经过一重循环，且不需要进行字符串比较的计算前缀函数算法。其复杂度为O(n)。

KMP算法

现在，通过getPi()函数，我们可以在线性时间复杂度下解决开头给出的问题。

记t.length()为$m$，p.length()为$n$。

构造串$p+\%+t$，其中$\%$为一个既不出现在$p$中也不出现在$t$中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始$n+1$个值（即属于字符串$p$和分隔符的函数值）后其余函数值的意义。根据定义，$\pi[i]$为右端点在$i$且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与$p$的前缀相同且右端点位于$i$的最长子串的长度。由于分隔符的存在，该长度不可能超过$n$。而如果等式$\pi[i]=n$成立，则意味着$p$完整出现在该位置（即其右端点位于位置$i$）。注意，该位置的下标是对字符串$p+\%+t$而言的。

因此如果在某一位置$i$有$\pi[i]=n$成立，则字符串$p$在字符串$t$的$i-(n-1)-(n+1)=i-2n$处出现。

KMP算法在O(m+n)的时间复杂度下解决了此问题。

例题

题目来自BUPT-ExitedOJ

题目描述

已知串s和t均由小写字母组成，且串s和t中可能包含重复字母。

试找出串t在串s中出现的所有位置。

输入格式

第一行为一个字符串s，由小写字母构成。(Len(s) < 1000000)
第二行为一个字符串t，由小写字母构成。(Len(t) < 1000000)

输出格式

输出若干行，为串t在串s中出现的所有位置，按从小往大依次输出。

Sample Input 1

acabaabaabcacaabc

abaabcac

Sample Output 1

6

Sample Input 2

aaaaa

a

Sample Output 2

1

2

3

4

5

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>

using namespace std;

struct str
{
    char ch[2000000 + 1]{ 0 };
    int pi[2000000 + 1]{ 0 };
    int length = 0;

    int getLength()
    {
        length = strlen(ch);
        return length;
    }

    void getPi(int length)
    {
        int i = 1;
        for (; i < length; i++)
        {
            int j = pi[i - 1];
            while (j > 0 && ch[i] != ch[j])
            {
                j = pi[j - 1];
            }
            if (ch[i] == ch[j])
            {
                j++;
            }
            pi[i] = j;
        }
    }
};

str s1, s2;

int main() {
    cin >> s1.ch;
    cin >> s2.ch;

    int subStringLength = s2.getLength();
    s2.ch[subStringLength] = '#';
    int textLength = s1.getLength();
    strncpy(s2.ch + subStringLength + 1, s1.ch, textLength);

    s2.getPi(subStringLength + textLength + 1);

    for (int i = subStringLength + 1; i < subStringLength + textLength + 1; i++)
    {
        if (s2.pi[i] == subStringLength)
        {
            cout << i - 2 * subStringLength + 1 << endl;
        }
    }

    return 0;
}

注：

我院数据结构课的要求是必须自己实现串的数据结构，但是可以调用C/C++库中的方法。

但是由此产生了一个问题：C++的数据结构由于被类封装，对数据结构的处理方法与数据结构本身是绑定在一起的。当使用自己定义的数据结构时，就无法使用数据结构自身的方法。但是C将数据结构与方法分离，我可以简便的使用<cstring>中的strlen()方法。

由此引出了OOP受到批评的原因之一：数据结构与方法是根本不同的元素，它们不应该被绑定在一起。用类封装不总是合适的。