Nice introduction in how search algorithms work
I found on the wikipedia page of the Rabin Karp String Search Algorithm a nice introduction in searching in general.
1 function NaiveSearch(string s[1..n], string sub[1..m]) 2 for i from 1 to n-m+1 3 for j from 1 to m 4 if s[i+j-1] ≠ sub[j] 5 jump to next iteration of outer loop 6 return i 7 return not found
This algorithm works well in many practical cases, but can exhibit relatively long running times on certain examples, such as searching for a string of 10,000 "a"s followed by a "b" in a string of 10 million "a"s, in which case it exhibits its worst-case Θ(mn) time.
The Knuth–Morris–Pratt algorithm reduces this to Θ(n) time using precomputation to examine each text character only once; the Boyer–Moore algorithm skips forward not by 1 character, but by as many as possible for the search to succeed, effectively decreasing the number of times we iterate through the outer loop, so that the number of characters examined can be as small as n/m in the best case. The Rabin–Karp algorithm focuses instead on speeding up lines 3-6.
Trackbacks
Verwenden Sie den folgenden Link zur Rückverlinkung von Ihrer eigenen Seite:
http://praktikanten.brueckenschlaeger.org/trackbacks?article_id=369