pythonmatchingbrute-force

Brute force pattern algorithm


Using Python, how would you implement a brute-force string matching algorithm? It should find a pattern (string of m characters) in a text (string of n characters). Verify your code with outputs from following test cases:

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

Solution

  • You can use

    pattern in text
    

    for this. If you need to implement the entire algorithm from scratch it's also rather easy:

    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
    

    Usage

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

    It should be noted that there are other algorithms that are going to be much more efficient, for example the famous Knuth-Morris-Pratt algorithm.