String matchingSunday algorithm 
The BoyerMoorealgorithm uses for its badcharacter heuristics the text symbol that has caused a mismatch. The Horspoolalgorithm uses the rightmost symbol of the current text window. It was observed by Sunday [Sun 90] that it may be even better to use the symbol directly right of the text window, since in any case this symbol is involved in the next possible match of the pattern.
Example:


 
(a) BoyerMoore  (b) Horspool  (c) Sunday  
In this example, t_{0}, ..., t_{4} = a b c a b is the current text window that is compared with the pattern. Its suffix a b has matched, but the comparison ca causes a mismatch. The badcharacter heuristics of the BoyerMoore algorithm (a) uses the "bad" text character c to determine the shift distance. The Horspool algorithm (b) uses the rightmost character b of the current text window. The Sunday algorithm (c) uses the character directly right of the text window, namely d in this example. Since d does not occur in the pattern at all, the pattern can be shifted past this position.
Like the BoyerMoore and the Horspool algorithm, the Sunday algorithm assumes its best case if every time in the first comparison a text symbol is found that does not occur at all in the pattern. Then the algorithm performs just O(n/m) comparisons.
In contrast to the BoyerMoore and the Horspool algorithm the pattern symbols need not be compared from right to left. They can be compared in an arbitrary order. For instance, this order can depend on the symbol probabilities, provided they are known. Then the least probable symbol in the pattern is compared first, hoping that it does not match, so that the pattern can be shifted
The following example shows the comparisons performed if symbol c of the pattern is compared first..
Example:
0  1  2  3  4  5  6  7  8  9  ... 

a  b  c  a  b  d  a  a  c  b  a 
b  c  a  a  b  
b  c  a  a  b 
The occurrence function occ required for the badcharacter heuristics is computed in the same way as in the BoyerMoore algorithm.
Given a pattern p, the following function sundayInitocc computes the occurrence function; it is identical to the function bmInitocc.
void sundayInitocc() { int j; char a; for (a=0; a<alphabetsize; a++) occ[a]=1; for (j=0; j<m; j++) { a=p[j]; occ[a]=j; } } 
Using a function matchesAt that compares the pattern with the text window in a certain manner depending on the implementation, the searching algorithm looks as follows:
void sundaySearch() { int i=0; while (i<=nm) { if (matchesAt(i)) report(i); i+=m; if (i<n) i=occ[t[i]]; } } 
After statement i+=m, it is necessary to check if the value of i is at most n1, since subsequently t[i] is accessed.
[Sun 90]  D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132142 (1990) 
[Web 1]  http://wwwigm.univmlv.fr/~lecroq/string/ 
Next: 
H.W. Lang Hochschule Flensburg lang@hsflensburg.de Impressum © Created: 31.01.2005 Updated: 29.05.2016 