原生字符串匹配算法

Question

以下是本机字符串匹配中非常着名的问题.请有人向我解释答案.

假设模式P中的所有字符都不同.演示如何加速NAIVE-STRING MATCHER在n字符文本T上及时运行O(n).

Answer 1

基本理念:

• 同时迭代输入和模式,将它们的字符相互比较
• 只要在两者之间得到不匹配的字符,就可以重置模式位置并保持输入位置不变

这是有效的,因为模式字符都是不同的,这意味着每当你有一个部分匹配时,就没有其他匹配重叠,所以我们可以从部分匹配的结尾开始查看.

这里有一些伪代码,不应该太难理解:

input[n]
pattern[k]
pPos = 0
iPos = 0
while iPos < n
  if pPos == k
    FOUND!
  if pattern[pPos] == input[iPos]
    pPos++
    iPos++
  else
    // if pPos is already 0, we need to increase iPos,
    //   otherwise we just keep comparing the same characters
    if pPos == 0
      iPos++
    pPos = 0

很容易看出,iPos至少每隔一个循环增加一次,因此最多可以2n循环运行,从而缩短运行时间O(n).