Note: This article is available in Chinese only. 本文暂无英文版本。
View original
20170801update：当时竟然没有强调 next 函数的含义？
next[i] 的含义是，i 之前的整个前缀中，最长的「前缀和后缀相同」的长度。
看图：
KMP 感觉是我学到现在最难懂的一个算法了 QAQ 为什么你们都那么强啊，看几个小时就看懂了……
先放一波我觉得值得看的资料： kmp算法讲解（配图比较全……） kmp学习资料2
说下我对 KMP 算法的理解：
理解 KMP 算法大概分成两个部分。
一部分是理解一个 naive 的 KMP 算法，可以叫 “fast slide” algorithm
思想大概就是，当 mismatch 发生时，我们并不是一无所有，而是知道 mismatch 发生前已匹配字符的信息。
然后知道这些信息我们可以做什么呢？
先观察一下最最暴力的求解字符串匹配的算法：
1//***********************************************************
2//brute force
3 n = T.length();
4 m = P.length();
5
6 i0 = 0; // Line P up with the first character of T
7 i = 0; // Start matching with first char in T
8 j = 0; // Start matching with first char in P
9
10 while ( i < n ) // Not all characters used
11 {
12 if ( T[i] == P[j] )
13 {
14 /* ===============================================
15 T[i] and P[j] match ==> try next pair
16 =============================================== */
17 i++; // Match next pair
18 j++;
19
20 if ( j == m )
21 return ( i0 ); // Match found at position i0 !!!
22 }
23 else
24 { /* ===========================================
25 T[i] ≠ P[j]:
26 1. Slide P up 1 position
27 2. restart from beginning of string
28 =========================================== */
29 i0 = i0 + 1; // Slide pattern P one character further
30
31 i = i0; // Restart matching at position i0 in T
32 j = 0; // Restart matching at position 0 in P
33 }
34 }
35
36 return -1; // Return not found
37 }这个算法低效在，当 mismatch 发生时，我只是往前移动了一个字符。
因此我们定义了 maxoverlap 函数。
**需要特别强调的是，**这样我们就可以利用 maxoverlap 函数来优化 mismatch 发生时移动的过程。
1 KMP( T, P )
2 {
3 int i0, i, j, m, n;
4
5 n = T.length();
6 m = P.length();
7
8 i0 = 0; // Line P up with the first character of T
9 i = 0; // Start matching with first char in T
10 j = 0; // Start matching with first char in P
11
12 while ( i < n ) // Not all characters used
13 {
14 if ( T[i] == P[j] )
15 {
16 i++; // Match next pair
17 j++;
18
19 if ( j == m )
20 return ( i0 ); // Match found atposition i0 !!!
21 }
22 else
23 { /* ===========================================
24 T[i] ≠ P[j]
25 =========================================== */
26
27 if ( j == 0 )
28 { /* ==============================================
29 First character already mismatched
30 We have NO prefix info. to work with...
31 =============================================== */
32 i0++; // Just slide P 1 character over
33 i = i0; //
34 j = 0;
35 }
36 else
37 {
38 prefix = P[ 0..(j-1) ]; // Prefix of pattern at the mismatch
39
40 k = MaxOverlap( prefix );
41
42 j = k;
43 i0 = (i - j);
44 // i is unchanged !
45 }
46 }
47 }
48
49 return -1; // No match found
50 }这样我们就得到了 “fast slide” algorithm 算法。
但是，能不能再给力一点呢？
我们发现，上述代码中，我们每次都要计算一次 maxoverlap 函数。
但是，一个字符串的子串个数是有限的。
我们能不能加速这个过程呢？
很容易想到预处理一波。
也就是求所谓的 failure function，中文应该叫失配函数……
所以第二部分就是如何快速求出失配函数
这也是我认为的 KMP 算法最精(nan)髓(dong)的地方。