Strings 2008 2 3: Difference between revisions
From MDWiki
Jump to navigationJump to search
ThomasHuber (talk | contribs) No edit summary |
ThomasHuber (talk | contribs) No edit summary |
||
Line 6: | Line 6: | ||
=== Simple python code === | |||
<pre> | |||
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) | |||
</pre> | |||
If the text is n characters long and the pattern is m characters long, it takes O(n*m) steps. | If the text is n characters long and the pattern is m characters long, it takes O(n*m) steps. | ||
Revision as of 04:54, 10 January 2008
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)
If the text is n characters long and the pattern is m characters long, it takes O(n*m) steps.
goto Visual comparison of strings
--ThomasHuber 13:07, 10 January 2008 (EST)