KMP算法
Knuth–Morris–Pratt algorithm
克努斯-莫里斯-普拉特 算法
algorithm kmp_search:
input:
an array of characters, S (the text to be searched)
an array of characters, W (the word sought)
output:
an array of integers, P (positions in S at which W is found)
an integer, nP (number of positions)
define variables:
an integer, j ← 0 (the position of the current character in S)
an integer, k ← 0 (the position of the current character in W)
an array of integers, T (the table, computed elsewhere)
let nP ← 0
while j < length(S) do
if W[k] = S[j] then
let j ← j + 1
let k ← k + 1
if k = length(W) then
(occurrence found, if only first occurrence is needed, m ← j - k may be returned here)
let P[nP] ← j - k, nP ← nP + 1
let k ← T[k] (T[length(W)] can't be -1)
else
let k ← T[k]
if k < 0 then
let j ← j + 1
let k ← k + 1
字符串查找算法
https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
https://zh.wikipedia.org/wiki/克努斯-莫里斯-普拉特算法
demo
https://www.nowcoder.com/question/next?pid=16778547&qid=369906&tid=36647493
https://www.nowcoder.com/questionTerminal/8f9ffcde7f644fd2ad093b6919b0c99d
refs
部分匹配表
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合;
"后缀"指除了第一个字符以外，一个字符串的全部尾部组合;
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
©xgqfrms 2012-2020
www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！