Strings 2008 2 3

Brute force (naive) search

The simplest, but also least efficient approach to text searching is to check whether the pattern matches the string at every possible position in the string. This is called the brute-force or naive string search algorithm. The procedure is illustrated below.

Simple python code

def naiveStringSearch(s, p):
    """native string search to find first occuranece of a pattern in a text"""

    if (len(p) > len(s)):
        return -1

    for i in range(len(s)-len(p)+1):   # all possible positions in text
        match = 1
        for j in range(len(p)):        # all positions in pattern
            if (s[i+j] != p[j]):
                match = 0              # mis-match
        if (match == 1):
            return i

    return -1




start = 'ATG'
dna = 'ATCGGCTAAATGGCTGCTATTAAGCT'

location = naiveStringSearch(dna, start)
print "The first start codon in the DNA sequence is at position %i" % (location+1)

Computational complexity

The runtime of the algorithm depends on both the length of the pattern and the length of the text string. If the text is n characters long and the pattern is m characters long, it takes O(n*m) computations.

Discovery question: Compare the runtimes of the naive string search algorithm with the python routine find in the string module. How does the string.find scale with pattern and text size? How do you think this is possible? Here's a python code stub and Herman Melville's Moby Dick as a large text.

goto Visual comparison of strings

--ThomasHuber 13:07, 10 January 2008 (EST)