I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page. And why with this rule we go to a linear time complexity?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The answer doesn't need to be a professional opinion explained in details, just how you think it may work! $\endgroup$– Andi DomiCommented Sep 20, 2016 at 15:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The algorithm is based on a simple principle. Suppose that we are trying to match a substring of length n. We are going to first look at character at index m. If that character is not in the string, we know that the substring we want can't start in characters at indices 1 2....n
If that character is in our string, we will assume that it is at the last place in our string that it can be. We will then jump back and start trying to match the string from that possible starting place. This piece of information is my first table.
Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match anand in ananand successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.
Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.
