h****p
发帖数: 87 | 1 研究下KMP算法，看到wiki上的解释有一点不是很理解 请大牛帮忙解释解释
算table如下：
algorithm kmp_table:
input:
an array of characters, W (the word to be analyzed)
an array of integers, T (the table to be filled)
output:
nothing (but during operation, it populates the table)
define variables:
an integer, pos ← 2 (the current position we are computing in T)
an integer, cnd ← 0 (the zero-based index in W of the next
character of the current candidate substring)
(the first few values are fixed but different from what the algorithm
might suggest)
let T[0] ← -1, T[1] ← 0
while pos < length(W) do
(first case: the substring continues)
if W[pos - 1] = W[cnd] then
let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
(second case: it doesn't, but we can fall back)
else if cnd > 0 then
let cnd ← T[cnd]
(third case: we have run out of candidates. Note cnd = 0)
else
let T[pos] ← 0, pos ← pos + 1
不理解的地方在second case： 为什么要把cnd = T[cnd]? 而不是直接把cnd=0？
想了很多例子还是不理解
谢谢 |
c***0
发帖数: 449 | 2 你直接回到0也可以，只是效率差一些，第二部是利用以前的计算结果，快速找到接下
来该和谁再比。你可以理解为计算Kmp的表格的时候也是kmp算法。 |
h****p
发帖数: 87 | 3 基本上都是要返回到0的，至少我还没想到反例 这样的话直接让cnd=0不是效率更好吗
【在 c***0 的大作中提到】
: 你直接回到0也可以，只是效率差一些，第二部是利用以前的计算结果，快速找到接下
: 来该和谁再比。你可以理解为计算Kmp的表格的时候也是kmp算法。
|
b*****n
发帖数: 143 | 4 What about this input string: "ABAABABX", and you want to calculate the last
element in the table?
【在 h****p 的大作中提到】
: 基本上都是要返回到0的，至少我还没想到反例 这样的话直接让cnd=0不是效率更好吗
|
c***0
发帖数: 449 | 5 举个简单地例子，abcabd，当你算d的时候，如果失败，你应该再比c，而不是比a，因
为ab是重复的，这就是第二部的意义。 |
h****p
发帖数: 87 | 6 nice example! thanks, u r right
last
【在 b*****n 的大作中提到】
: What about this input string: "ABAABABX", and you want to calculate the last
: element in the table?
|
h****p
发帖数: 87 | 7 例子有点出入，这里默认不算最后一位的，anyway是这个意思，多谢
【在 c***0 的大作中提到】
: 举个简单地例子，abcabd，当你算d的时候，如果失败，你应该再比c，而不是比a，因
: 为ab是重复的，这就是第二部的意义。
|
c***0
发帖数: 449 | 8 最后一位不用算是啥意思，那你最后一位如果匹配失败了，该继续匹配哪位呢？
【在 h****p 的大作中提到】
: 例子有点出入，这里默认不算最后一位的，anyway是这个意思，多谢
|
A*********c
发帖数: 430 | 9 不能直接回到0.
cnd ← T[cnd]的含义是，找到当前“匹配失败的模式串”的最长的一个proper suffix
, 然后再次尝试匹配。
T这个T vector相当于建了一个Nondeterministic finite automata，直接回到zero的
话，相当于直接回到状态0，
中间的有用的suffix信息都没有用到。
整个过程不停地回溯，到0的时候意味尝试部分匹配彻底失败了，只能从头开始。
【在 h****p 的大作中提到】
: 研究下KMP算法，看到wiki上的解释有一点不是很理解 请大牛帮忙解释解释
: 算table如下：
: algorithm kmp_table:
: input:
: an array of characters, W (the word to be analyzed)
: an array of integers, T (the table to be filled)
: output:
: nothing (but during operation, it populates the table)
: define variables:
: an integer, pos ← 2 (the current position we are computing in T)
|
