3

我在 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

我的代码i 在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
4

2 回答 2

2

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

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之间有一个跳跃。你能解释一下你的偏移表的逻辑吗？如果我能在此处找出逻辑中的任何错误，我将更新此答案。

于 2019-08-04T23:12:52.640 回答
0

不确定它是否适合max之后，但我想你应该重置i到它在开始时内部之前的值（如果你的针大小是 2，那么它i -= 1发生了一次），更新计数器然后中断：

        if j == 0:
            i += len(needle) - 1
            counter += 1
            break
        i -= 1
        j -= 1
于 2019-08-04T22:28:08.953 回答