如果不一致,则从S的第 2 个字符开始重复整个过程;如果还不行就再从第三个字符开始……总之就是跳回到本次匹配S开始处的下一个字符,然后重新开始整个匹配过程
如果到最后都没有匹配上完整的W,则说明S中根本无法找到...“Great” 的后缀集合为:{“reat”, “eat”, “at”, “t” }。
前后缀集合交集中的最长元素
那我们来看看ababab。...它的前缀集合是:{“ababa”, “abab”, “aba”, “ab” , “a”};而它的后缀集合为:{“babab”, “abab”, “bab”, “ab”, “b”}。...Partial Match Table (PMT)
综上,我们需要做的就是将 w 的所有前缀罗列出来,然后分别统计这一个个前缀字符串的前缀集合与后缀集合并集中子串的最大长度,我们把这个长度称为 Partial...中查找已经匹配上的子串的最后一个字符对应的 PM value,用匹配字串的长度减掉 PM value 的值,就是 s 前进的步数。