谁可以给我解释一下这个?我一直在阅读它,但仍然很难遵循。
文字:ababdbaababa 模式:ababa
ababa的表是-1 0 0 1 2。
我想我了解表的构造方式,但是一旦发生不匹配,我就不知道如何进行移位。似乎我们在移位时甚至不使用表格?
我们什么时候使用桌子?
发生不匹配时使用该表。让我们将模式应用于您的文本:
您开始将文本与模式匹配,并从第一个位置开始测试模式是否可以在文本中显示。你比较text[1]有pattern[1]和原来是一场比赛。你做同样的text[2],text[3]和text[4]。
text[1]
pattern[1]
text[2]
text[3]
text[4]
当您想text[5]与之匹配时,pattern[5]没有匹配项(d<> a)。然后,您知道您的模式将不会从第一个位置开始。然后,您可以重新开始位置2的匹配,但是效率不高。您 现在 可以 使用该表 。
text[5]
pattern[5]
d
a
错误发生在,pattern[5]所以您转到table[5]2。这表明您可以使用2个 已经匹配的字符 再次开始在当前位置进行 匹配 。不必开始匹配位置2,您可以从先前的位置(1)+ table[5](2)= 3开始。的确,如果我们看一下text[3]和text[4],我们将看到它pattern[1]和和相等pattern[2]。
table[5]
pattern[2]
表格中的数字告诉您发生错误时已经匹配了多少个位置。在这种情况下,下一个模式的2个字符已经匹配。然后,您可以立即开始匹配位置3,并跳过位置2(因为从位置[2]开始找不到该模式)。