下面是我阅读 Jake Boxer 的文章时做的笔记。应该可以帮助理解。
KMP的关键是“部分匹配表”。而理解KMP的关键是领会“部分匹配表”中值的含义。下面看看模式字符串”abababca”的部分匹配表。
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
对于一个8个字符长度的模式串,部分匹配表长度也为8. 继续阅读 »
最新评论