find the starting index in string haystack[] that matches the search word P[] @param haystack The text to be searched @param needle The pattern to be searched for @return A list of starting indices where the pattern is found
(final String haystack, final String needle)
| 19 | * @return A list of starting indices where the pattern is found |
| 20 | */ |
| 21 | public static List<Integer> kmpMatcher(final String haystack, final String needle) { |
| 22 | List<Integer> occurrences = new ArrayList<>(); |
| 23 | if (haystack == null || needle == null || needle.isEmpty()) { |
| 24 | return occurrences; |
| 25 | } |
| 26 | |
| 27 | final int m = haystack.length(); |
| 28 | final int n = needle.length(); |
| 29 | final int[] pi = computePrefixFunction(needle); |
| 30 | int q = 0; |
| 31 | for (int i = 0; i < m; i++) { |
| 32 | while (q > 0 && haystack.charAt(i) != needle.charAt(q)) { |
| 33 | q = pi[q - 1]; |
| 34 | } |
| 35 | |
| 36 | if (haystack.charAt(i) == needle.charAt(q)) { |
| 37 | q++; |
| 38 | } |
| 39 | |
| 40 | if (q == n) { |
| 41 | occurrences.add(i + 1 - n); |
| 42 | q = pi[q - 1]; |
| 43 | } |
| 44 | } |
| 45 | return occurrences; |
| 46 | } |
| 47 | |
| 48 | // return the prefix function |
| 49 | private static int[] computePrefixFunction(final String p) { |