KMP算法

串的朴素模式匹配算法

什么是字串匹配：

在主串中找到与模式串相同的字串并返回其位置，如主串google、模式串gle，则结果为3

算法思路：

相当于拿着模式串和主串对齐，对比其第一个字符。不相等则模式串往右移一位，相等则匹配剩下的字符，计算方式如下：
1 2 3 4 5 6 7 S w a n g d a o T g d a

ST​1wg​2ad​3na​4g​5d​6a​7o​​
k 1 2 3 4 4 4 4 i 1 2 3 4 5 6 7 j 1 1 1 1 2 3 4

k1234444i1234567j1111234" role="presentation">kij111221331441452463474$$\begin{array}{|cccccccc|}\hline k& 1& 2& 3& 4& 4& 4& 4\\ i& 1& 2& 3& 4& 5& 6& 7\\ j& 1& 1& 1& 1& 2& 3& 4\\ \hline\end{array}$$

kij​111​221​331​441​452​463​474​​

缺点：

当某些字串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加

朴素模式匹配算法代码：

// S为主串，T为模式串
int Index(String S, String T) {
    // i用来遍历主串
    // k用来标记当前匹配串的第一个字符
    // j用来遍历模式串
    int i = k = j = 1;
    while (i <= S.length && j <= T.length) {
        if (S[i] == T[j]) {
            i++;
            j++;
        } else {
            k++;
            i = k;
            j = 1;
        }
    }
    // 用j是否超出边界作为成功标志
    if (j > T.length) {
        return k;
    } else {
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

KMP算法

优点：

在上述朴素模式匹配算法中，当模式串第一个字符匹配时，j和i都继续++去匹配剩下的字符，但一旦当模式串第j个字符不匹配时，i和j都回溯，即模式串往右移动一格。但是其实大部分时候可以通过计算不回溯这么多（某些模式串中回溯到特点值就可保证最短不匹配）。例如：模式串google当j=5时不匹配，此时可发现只要i不变，j回溯到1即可满足最短不匹配，即模式串往右移了4格。KMP算法就是在i不回溯的情况下给出一个next数组用于表示当不匹配时j应该回溯到哪里，这样在模式匹配算法的基础上进一步优化了性能，解决了i经常回溯的问题。

求next数组：

n e x t [ j ] = { 0 , 当j=1时 1 , 当j=2时 前 j − 1 个 字 串 的 最 长 相 等 前 后 缀 长 度 + 1 , 当j>2时 next[j] =

next[j]=⎩⎪⎨⎪⎧​0,1,前j−1个字串的最长相等前后缀长度+1,​当j=1时当j=2时当j>2时​
前j-1个字串的最长相等前后缀长度：当前j-1个字串为abcab时，ab为前缀和后缀最长相等部分，结果为2；当前j-1个子串为abc时，没有前后缀相等部分，结果为0。
序 号 j 1 2 3 4 5 6 模 式 串 a b a b a a n e x t [ j ] 0 1 1 2 3 4

序号j123456模式串ababaanext[j]011234" role="presentation">序号j模式串next[j]1a02b13a14b25a36a4$$\begin{array}{|ccccccc|}\hline 序号j& 1& 2& 3& 4& 5& 6\\ 模式串& a& b& a& b& a& a\\ next[j]& 0& 1& 1& 2& 3& 4\\ \hline\end{array}$$

序号j模式串next[j]​1a0​2b1​3a1​4b2​5a3​6a4​​

KMP算法代码：

int Index_KMP(String S, String T, int next[]) {
    int i = j = 1;
    while (i <= S.length && j <= T.length) {
        if (j==0 || S[i] == T[j]) {
            i++;
            j++;
        } else {
            j = next[j];        // i不回溯，j查找next数组回溯
        }
    }
    if (j > T.length) {
        return i - T.length;    // 匹配成功
    } else {
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMP算法的优化：

当模式串为google，j=4时。原KMP算法的next[4]=1，但是其实此处不需要再重新匹配第一位，所以应该优化为next[4]＝0。因此引入next的优化数组nextVal。
n e x t V a l [ j ] = { 0 , 当j=1时 n e x t [ j ] , 当j>1 且 T[next[j]]!=T[j]时 n e x t V a l [ n e x t [ j ] ] , 当j>1 且 T[next[j]]==T[j]时 nextVal[j] =

nextVal[j]=⎩⎪⎨⎪⎧​0,next[j],nextVal[next[j]],​当j=1时当j>1 且 T[next[j]]!=T[j]时当j>1 且 T[next[j]]==T[j]时​
序 号 j 1 2 3 4 5 6 模 式 串 a b a b a a n e x t [ j ] 0 1 1 2 3 4 n e x t V a l [ j ] 0 1 0 1 0 4

序号j123456模式串ababaanext[j]011234nextVal[j]010104" role="presentation" style="position: relative;">序号j模式串next[j]nextVal[j]1a002b113a104b215a306a44$$\begin{array}{|ccccccc|}\hline 序号j& 1& 2& 3& 4& 5& 6\\ 模式串& a& b& a& b& a& a\\ next[j]& 0& 1& 1& 2& 3& 4\\ nextVal[j]& 0& 1& 0& 1& 0& 4\\ \hline\end{array}$$

序号j模式串next[j]nextVal[j]​1a00​2b11​3a10​4b21​5a30​6a44​​