Simplified Boyer-Moore algorithm

After reading an article about substring search algorithms in a string , I found that it does not talk about the Boyer-Moore algorithm. A couple of words about him are still there, namely, it is said that the Boyer-Moore algorithm has earned itself the title of “default algorithm”, because on average it gives the best search time (with which I completely agree). Under the cat, a simplified version of this algorithm is described. In principle, most likely studied this algorithm in the 1st or 2nd year of a university (like me), so they can skip this article, there is nothing new here.

Algorithm

This algorithm is also known as the Boyer-Moore-Horspool algorithm. The algorithm procedure is very simple. First, an offset table is constructed for each character. Then the initial line and the template are combined at the beginning, the comparison is carried out by the last character. If the last characters match, then the comparison follows the penultimate character and so on. If the characters did not match, then the pattern is shifted to the right, by the number of positions taken from the displacement table for the character from the source string, and then the last characters of the source string and pattern are compared again. And so on, until the pattern completely matches the substring of the source string, or until the end of the string is reached.

Offset Table

The offset table is built on the principle of "skip as many characters as possible, but no more than that." For example, if at some step of the algorithm the last characters did not match, and the character located in the source line is not present in the template at all, then it is clear that you can move right to the full length of the template, without any fear. In the general case, each symbol is assigned a value equal to the difference between the length of the template and the serial number of the symbol (if the symbol is repeated, then the rightmost occurrence is taken). It is clear that this value will be exactly equal to the ordinal number of the symbol, if we count from the end of the line, which makes it possible to shift to the right by the maximum possible number of positions.

Illustration

To make it completely clear, consider the operation of the algorithm as an example:
Let the source string be “somestring” and the pattern equal to “string”. Now we are building the offset table, it will be equal to the length of the pattern for all characters that do not appear in the pattern, and the serial number from the end for the rest (except the last one, the length of the pattern is also taken for it): Now we combine our lines: Compare the last characters: we see, that "t" is not equal to "g". We take the offset value for the “t” character, it is 4. We shift the line to the right by 4 positions, and voila: Next, the algorithm will compare the characters from the last to the first in the template with the corresponding characters in the original string. As soon as he compares the latter, it will be found out that this is the first occurrence.

s->5
t->4
r->3
i->2
n->1
g->6


  somestring
  string



  somestring
      string


The code

Wrote some Java code to spice up this theory. Any comments are welcome.

/**
 * Возвращает индекс первого вхождения строки template в строку source, или
 * -1, в случае если вхождение не найдено.
 * 
 * @param source
 *            исходная строка, в которой ищется вхождение шаблона.
 * @param template
 *            шаблон строки, которая ищется в строке source.
 * @return индекс первого вхождения строки template в строку source, или -1,
 *         в случае если вхождение не найдено.
 */
public int getFirstEntry(String source, String template) {
	int sourceLen = source.length();
	int templateLen = template.length();
	if (templateLen > sourceLen) {
		return -1;
	}
	HashMap offsetTable = new HashMap();
	for (int i = 0; i <= 255; i++) {
		offsetTable.put((char) i, templateLen);
	}
	for (int i = 0; i < templateLen - 1; i++) {
		offsetTable.put(template.charAt(i), templateLen - i - 1);
	}
	int i = templateLen - 1;
	int j = i;
	int k = i;
	while (j >= 0 && i <= sourceLen - 1) {
		j = templateLen - 1;
		k = i;
		while (j >= 0 && source.charAt(k) == template.charAt(j)) {
			k--;
			j--;
		}
		i += offsetTable.get(source.charAt(i));
	}
	if (k >= sourceLen - templateLen) {
		return -1;
	} else {
		return k + 1;
	}
}

Conclusion

It is said that such a modification of the Boyer-Moore algorithm handles random texts better than the original algorithm itself. However, the worst-case difficulty rating is still worse. But unlike the original algorithm, no complicated calculations are required here - only a table of offsets is constructed, which is not so difficult to implement.