WOLFRAM|DEMONSTRATIONS PROJECT

Brute-Force String Matching

​
outer loop n
inner loop m
automatic mismatch shift of selected input string
random seed
text input string
G
G
C
T
A
A
G
A
A
G
A
C
C
C
G
A
T
T
A
A
T
T
C
G
C
T
G
G
A
G
A
C
A
A
T
G
C
G
A
C
T
A
A
G
G
G
G
G
T
A
G
A
G
G
T
G
T
A
T
A
selected part of input string
GGCT
selected text character
G
​
character mismatch
string mismatch
​
selected pattern character
T
input pattern
TCCG
​
positions in preliminary result
None
Brute-force string matching compares a given pattern with all substrings of a given text. Those comparisons between substring and pattern proceed character by character unless a mismatch is found. Whenever a mismatch is found, the remaining character comparisons for that substring are dropped and the next substring can be selected immediately. The visualization of this sliding selection window shows the selected characters in blue. The characters which are currently compared are printed in magenta. Note that brute-force searching usually involves automatic shifts upon mismatch to avoid unnecessary comparisons.