KMP 主要应用在字符串匹配上。
KMP 的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。
说明 借用了 这篇博客 的一些插图和理解
next 数组就是一个前缀表(prefix table):前缀表是用来回退的,它记录了模式串与主串 (文本串) 不匹配的时候,模式串应该从哪里开始重新匹配。
假设 匹配串 S, 模式串 T
最长公共前后缀 : ABCAB 公共前后缀 是 AB ABABA 公共前后缀 是 ABA ABCABC 公共前后缀 是 ABC
如图,S[3]!=T[3](i=3,j=3),但前面的 ABA 有公共前后缀 A (最长公共前后缀不能等于前面的串长),长度为 1,所以把 j 移到 1(前缀移到后缀处), 如下图
又比如 下图中,S[5]!=T[5](i=5,j=5),有公共前后缀 AB,长度 2
将 j 移到 2 (i=5,j=2)
所以,重点要求 next 数组:
next[i] : 满足 x[i-k…i-1]=x[0…k-1] 的最大 k 值 (最长公共前后缀的长度)
考虑四种情况:
① j = 0 , 如果不匹配,j 已经在最左边,无法回退,所以要右移,即初始化 next [ 0 ] = -1
② j = 1 , 如果不匹配,只能左移到 0 ,所以 next [ 1 ] = 0
③ X [ k ] = X [ j ] 匹配到这个位置说明失配位置前 公共前后缀相等,即 X [ 0…k-1 ] = X [ j-k…j-1] (k 为公共前后缀长度) 那么,X [ 0…k ] = X [ j-k…j ] 所以,next [ j+1 ] = k+1 (数组下标从 0 开始,长度为 k+1)
④ X [ k ] != X [ j ] next[i] : 满足 x[j-k…i-1]=x[0…j-1] 的最大 k 值 (k 为最长公共前后缀) 此时,将前缀移到后缀位置 ,即指针前移到最长公共前后缀的长度位置,可以得出: k = next [ k ]
不过,这样求得的 next 数组还有缺陷:
按照前述,j 移到 最长公共前后缀长度 1 的位置:
这一步是完全没有意义的。因为后面的 B 已经不匹配了,那前面的 B 也一定是不匹配的,即 X[ j ] = X[ next[ j ] ] 的情况没有意义
代码随想录动图示例:
代码 GO 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 func getNext (next []int , s string ) { i, j := 0 , -1 next[0 ] = j for i < len (s) { for j !=-1 && s[i] != s[j] { j = next[j] } i++ j++ if i >= len (s) || j >= len (s) { return } if s[i] == s[j] { next[i] = next[j] } else { next[i] = j } } } func strStr (haystack string , needle string ) int { if len (needle) == 0 { return 0 } next := make ([]int , len (needle)) getNext(next, needle) i, j := 0 , 0 for i < len (haystack) && j < len (needle) { for j !=-1 && haystack[i] != needle[j] { j = next[j] } i++ j++ } if j == len (needle) { return i - j } else { return -1 } }
C++ 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 int nx[maxn];void getnx (string x) { int m=x.size (); int i,j; j=nx[0 ]=-1 ; i=0 ; while (i<m){ while (-1 !=j && x[i]!=x[j]) j=nx[j]; if (x[++i]==x[++j]) nx[i]=nx[j]; else nx[i]=j; } } int kmp (string s, string t) { int n=s.size (); int m=t.size (); int i=0 ,j=0 ; getnx (t); while (i<n && j<m) { while (-1 !=j && s[i]!=t[j]) j=nx[j]; i++; j++; } if (j==m) return i-j; else return -1 ; }
性质 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环。
即最小的循环节
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 func getNext (next []int , s string ) { i, j := 0 , -1 next[0 ] = j for i < len (s) { for j != -1 && s[i] != s[j] { j = next[j] } i++ j++ next[i] = j } } func repeatedSubstringPattern (s string ) bool { if len (s) == 0 { return false } next := make ([]int , len (s)+1 ) getNext(next, s) l := len (s) if next[l] != 0 && l%(l-next[l]) == 0 { return true } return false }