algorithm - 本机字符串匹配算法

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).

Answer 2

当 NAIVE-STRING-MATCHER 中的 T[i] 和 P[j] 不匹配时，我们可以跳过 T[i] 之前的所有字符，并从 T[i + 1] 开始与 P[1] 进行新的匹配。

天真的字符串匹配器（T，P）

1 n 长[T]

2米长[P]

3 代表 s 0 到 n - m

4 如果 P[1 . . m] = T[s + 1 。. 小号+米]

5 然后打印 "Pattern occur with shift" s

Answer 3

Python 2.7 中的朴素字符串搜索算法实现： https ://gist.github.com/heyhuyen/4341692

在实现 Boyer-Moore 的字符串搜索算法的过程中，我决定使用我原来的朴素搜索算法。它被实现为一个实例方法，该方法接受一个要搜索的字符串。该对象有一个属性“模式”，它是要匹配的模式。

1) 这是搜索方法的原始版本，使用双 for 循环。调用 range 和 len

def search(self, string):
    for i in range(len(string)):
        for j in range(len(self.pattern)):
            if string[i+j] != self.pattern[j]:
                break
            elif j == len(self.pattern) - 1:
                return i
    return -1

2) 这是第二个版本，使用双 while 循环。稍微快一点，不调用范围

def search(self, string):
    i = 0
    while i < len(string):
        j = 0
        while j < len(self.pattern) and self.pattern[j] == string[i+j]:
            j += 1
        if j == len(self.pattern):
            return i
        i += 1
    return -1

3) 这是原始的，用 xrange 替换范围。比前两个都快。

def search(self, string):
    for i in xrange(len(string)):
        for j in xrange(len(self.pattern)):
            if string[i+j] != self.pattern[j]:
                break
            elif j == len(self.pattern) - 1:
                return i
    return -1

4）在局部变量中存储值=赢！使用双 while 循环，这是最快的。

def search(self, string):
    len_pat = len(self.pattern)
    len_str = len(string)
    i = 0
    while i < len_str:
        j = 0
        while j < len_pat and self.pattern[j] == string[i+j]:
            j += 1
        if j == len_pat:
            return i
        i += 1
    return -1