python - Boyer moore 算法 - 计算所有匹配的子串

Question

我正在用 python 实现 boyer moore 算法，我需要计算一个子串在一个字符串中出现了多少次。

我的字符串存储在一个向量中:

string = ['A', 'B', 'B', 'C', 'F', 'D', 'B', 'B']

针也是一个向量:

needle = ['B', 'B']

我的问题是:

我实现的算法只返回针第一次出现的索引。在上面的示例中，它返回 1，但是，正如我之前所说，我需要每次都计算针是否出现在数组中，并期望它返回 2；

示例和预期返回

1

haystack = ['A', 'B', 'B', 'C', 'F', 'D', 'B', 'B']
needle = ['B', 'B'] 
expected return = 2

2

haystack = ['A', 'F', 'T', 'C', 'B', 'F', 'T', 'a', 'F', 'T']
needles = ['F', 'T']
expected return = 3

我的代码 我在 search 函数中，我尝试更改 return i (索引)，使用 counter += 1 来计算匹配的针数, 但是，如果我这样做，它会给我以下错误:

Traceback (most recent call last):
  File "booyer-moore.py", line 103, in <module>
    main(files)
  File "booyer-moore.py", line 98, in main
    index = search(haystack, needle)
  File "booyer-moore.py", line 18, in search
    i += max(offset_table[len(needle) - 1 - j], character_table.get(haystack[i]))
IndexError: list index out of range

def search(haystack, needle):
    counter = 0
    if len(needle) == 0:
        return 0
    character_table = createCharacterTable(needle)
    offset_table = createOffsetTable(needle)

    i = len(needle) - 1

    while i < len(haystack):
        j = len(needle) - 1
        while needle[j] == haystack[i]:
            if j == 0:
                return i
                # counter += 1
            i -= 1
            j -= 1
        i += max(offset_table[len(needle) - 1 - j], character_table.get(haystack[i]))
    return counter


def createCharacterTable(needle):
    table = {}
    for i in range(len(needle) - 1):
        table[needle[i]] = len(needle) - 1 - i
    return table


def createOffsetTable(needle):
    table = []
    lastPrefixPosition = len(needle)
    for i in reversed(range(len(needle))):
        if isPrefix(needle, i + 1):
            lastPrefixPosition = i + 1
        table.append(lastPrefixPosition - i + len(needle) + 1)
    for i in range(len(needle) - 1):
        slen = suffixLength(needle, i)
        table[slen] = len(needle) - 1 - i + slen
    return table


def isPrefix(needle, position):
    j = 0
    for i in range(position, len(needle)):
        if needle[i] != needle[j]:
            return False
        j += 1
    return True


def suffixLength(needle, position):
    length = 0
    j = len(needle) - 1
    for i in reversed(range(position + 1)):
        if needle[i] == needle[j]:
            length += 1
        else:
            break
        j -= 1
    return length

Answer 1

在您的解决方案中发现了几个错误，我已经纠正了这些错误。

def search(haystack, needle):
    if len(needle) == 0:
        return 0
    character_table = createCharacterTable(needle)
    offset_table = createOffsetTable(needle)
    i = len(needle) - 1
    while i < len(haystack):
        j = len(needle) - 1
        while needle[j] == haystack[i]:
            if j == 0:
                yield i
                break
            i -= 1
            j -= 1
        if(character_table.get(haystack[i])):
            i += max(character_table.get(haystack[i]),offset_table[len(needle) - 1 - j])
        else:
            i += offset_table[len(needle) - 1 - j]

haystack = ['A', 'F', 'T', 'C', 'B', 'F', 'T', 'a', 'F', 'T']
needle = ['F', 'T']
generator=search(haystack,needle)
for i in generator:
    print("Result: "+str(i))

返回多个解决方案的问题可以通过使用生成器来解决，即产生值而不是返回它们。

为您的 character_table.get(haystack[i]) 添加了一个检查，因为我不断收到此错误，因为如果不匹配，您的 character_table 字典中的值不存在。

i += max(character_table.get(haystack[i]),offset_table[len(needle) - 1 - j])

TypeError: '>' not supported between instances of 'int' and 'NoneType'

结果

Result: 1
Result: 5

现在我打印了你的 offsetTable，它给了我 [1, 5] 这对我来说不正确。在执行期间打印 i 和 j 的值我得到:

{'F': 1} [1, 5]
j is 1
i is 2
Result: 1
j is 0
i is 6
Result: 5
j is 0
i is 10

所以在索引 6 和 10 之间有一个跳跃。你能解释一下你的偏移表的逻辑吗？如果我能找出此处逻辑中的任何错误，我将更新此答案。