暴力模式算法

Question

使用Python，如何实现暴力字符串匹配算法？它应该在文本（n 个字符的字符串）中找到一个模式（m 个字符的字符串）。使用以下测试用例的输出验证您的代码：

Test case#1:
Text: 10110100110010111
Pattern: 001011

Test case#2:
Text: It is never too late to have a happy childhood
Pattern: happier

Test case#3:
Text: NOBODY_NOTICED_HIM 
Pattern: NOT

Answer 1

你可以使用

pattern in text

为此。如果您需要从头开始实现整个算法，这也相当简单：

def contains(text, pattern):
    for i in range(len(text)):
        for j in range(len(pattern)):
            if i + j >= len(text):
                break
            if text[i + j] != pattern[j]:
                break
        else:
            return True
    return False

使用方法

contains('10110100110010111', '001011') # True
contains('It is never too late to have a happy childhood', 'happier') # False

应该指出的是，还有其他算法会更加高效，例如著名的 Knuth-Morris-Pratt 算法。