In computer science, the Raita algorithm is a string searching algorithm which improves the performance of Boyer–Moore–Horspool algorithm. This algorithm preprocesses the string being searched for the pattern, which is similar to Boyer–Moore string-search algorithm. The searching pattern of particular sub-string in a given string is different from Boyer–Moore–Horspool algorithm. This algorithm was published by Timo Raita in 1991.[1]
Raita algorithm searches for a pattern "P" in a given text "T" by comparing each character of pattern in the given text. Searching will be done as follows. Window for a text "T" is defined as the length of "P".
If everything in the pre-check is successful, then the original comparison starts from the second character to last but one. If there is a mismatch at any stage in the algorithm, it performs the bad character shift function which was computed in pre-processing phase. Bad character shift function is identical to the one proposed in Boyer–Moore–Horspool algorithm.[1]
A modern formulation of a similar pre-check is found in, a linear/quadratic string-matcher, in libc++ and libstdc++. Assuming a well-optimized version of, not skipping characters in the "original comparison" tends to be more efficient as the pattern is likely to be aligned.[2]
/* Preprocessing: the BMH bad-match table. */static inline void preBmBc(char *pat, size_t lpat, ptrdiff_t bmBc[])
void RAITA(char *pat, size_t lpat, char *s, size_t n)
Pattern: abddb
Text:
Pre- Processing stage: a b d 4 3 1
Attempt 1: ....b Shift by 4 (bmBc[a])
Comparison of last character of pattern to rightmost character in the window. It's a mismatch and shifted by 4 according to the value in pre-processing stage.
Attempt 2: A.d.B Shift by 3 (bmBc[b])
Here last and first character of the pattern are matched but middle character is a mismatch. So the pattern is shifted according to the pre-processing stage.
Attempt 3: ABDDB Shift by 3 (bmBc[b])
We found exact match here but the algorithm continues until it can't move further.
Attempt 4: ....b Shift by 4 (bmBc[a])
At this stage, we need to shift by 4 and we can't move the pattern by 4. So, the algorithm terminates. Letters in capital letter are exact match of the pattern in the text.