|
1234567891011121314151617181920212223 |
- * Compile: `javac *.java`
- * Run test case: `./test <test dir>`
- * test 1: no matches (empty haystack)
- * test 2: no matches (empty needle)
- * test 3: "cog" (0-2), "cag"(8-10)
- * test 4: "horse" (0-4), "house"(5-9)
- * test 5: "this\nis\ntext" (0-11), "this is text" (13-24)
- * Main.java contains the main method.
- * I have assumed '_' should match a single character (like . in regex),
- not any number of characters (like * in bash).
- * My code is heavily influenced by the explanation of Boyer Moore Horspool
- in lecture 10.
- http://www.uio.no/studier/emner/matnat/ifi/INF2220/h16/undervisningsmaterialet/lecture10.pdf
-
- # Explanation of why it works
-
- The only change I made from standard Boyer Moore Horspool is that
- instead of checking whether a position in the needle matches the corresponding
- position in the haystack, I check if a positiion in the needle matches
- either '_' or the corresponding position in the heystack.
- I also modified it such that instead of returning on the first match,
- it just adds the match to an array, breaks out of the inner for loop, and
- goes on to find the next match.
|