Boyer-Moore tweak

William Fiset · William Fiset · commit bfcd6de9ac4b · 2020-06-07T23:19:28.000-07:00
diff --git a/src/main/java/com/williamfiset/algorithms/strings/BoyerMooreStringSearch.java b/src/main/java/com/williamfiset/algorithms/strings/BoyerMooreStringSearch.java
@@ -35,6 +35,7 @@ public List<Integer> findOccurrences(String text, String pattern) {
 
     int n = pattern.length();
     for (int textIndex = n - 1, patternIndex = n - 1; textIndex < text.length(); ) {
+      // Found a match!
       if (patternIndex >= 0 && pattern.charAt(patternIndex) == text.charAt(textIndex)) {
         if (patternIndex == 0) {
           occurrences.add(textIndex);
@@ -43,7 +44,7 @@ public List<Integer> findOccurrences(String text, String pattern) {
         }
         patternIndex--;
       } else {
-        textIndex += n - min(max(patternIndex, 0), 1 + skipTable[text.charAt(textIndex)]);
+        textIndex += n - min(max(patternIndex, 0), skipTable[text.charAt(textIndex)] + 1);
         patternIndex = n - 1;
       }
     }

Original file line number	Diff line number	Diff line change
`@@ -35,6 +35,7 @@ public List<Integer> findOccurrences(String text, String pattern) {`
`35`	`35`
`36`	`36`	`int n = pattern.length();`
`37`	`37`	`for (int textIndex = n - 1, patternIndex = n - 1; textIndex < text.length(); ) {`
	`38`	`+ // Found a match!`
`38`	`39`	`if (patternIndex >= 0 && pattern.charAt(patternIndex) == text.charAt(textIndex)) {`
`39`	`40`	`if (patternIndex == 0) {`
`40`	`41`	`occurrences.add(textIndex);`
`@@ -43,7 +44,7 @@ public List<Integer> findOccurrences(String text, String pattern) {`
`43`	`44`	`}`
`44`	`45`	`patternIndex--;`
`45`	`46`	`} else {`
`46`		`- textIndex += n - min(max(patternIndex, 0), 1 + skipTable[text.charAt(textIndex)]);`
	`47`	`+ textIndex += n - min(max(patternIndex, 0), skipTable[text.charAt(textIndex)] + 1);`
`47`	`48`	`patternIndex = n - 1;`
`48`	`49`	`}`
`49`	`50`	`}`