In celebration... here's Boyer Moore
The exams are over. I got 2.7 on Data Communication, 2.7 on Statistics and 2.0 on Computer Architecture (which would be C+ and B, respectively). Now I have some time to myself. To celebrate that, I fiddled a bit with PHP and implemented a text search algorithm I'd learned. It's called the Boyer Moore Sunday algorithm, and works as follows:
- Begin with the offset 0.
- Test the substring of haystack that begins on offset:
- Begin with needle-offset 0.
- Compare the corresponding characters of needle and the substring of haystack.
- Continue with 4. until the string is found or there is a mismatch.
- If there is a mismatch, examine the character in haystack immediately after the substring.
- Take the last position of this character in needle, or -1 if it does not occur.
- Shift the offset in haystack to the right by the length of needle, and to the left by the position you just calculated.
- Continue with 2.
The implementation is here. Note that PHP differs from compiled languages in some syntax points - for example, a String is simply an array of characters and can be treated as such. The return value is typeless, it can be a boolean or an integer.