CODEWITHSUNDEEP
pythonmatchingbrute-force
NoviceCoder
NoviceCoder

Reputation: 11

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

Upvotes: 0

Views: 2664

Answers (1)

Virtuoz
Virtuoz

Reputation: 914

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.

Upvotes: 0

Related Questions