View Javadoc
1   package ch.hslu.exercises.sw13.ex3;
2   
3   public class KMPSearch {
4   
5       public static int kmpSearch(final String searchString, final String pattern) {
6           final int n = searchString.length();
7           final int m = pattern.length();
8           int i = 0; // index to string searchString
9           int j = 0; // index to pattern pattern respectively state
10          // 1. generate next
11          int[] next = initNext(pattern);
12          // 2. search for pattern
13          do {
14              if ((j == -1) || (searchString.charAt(i) == pattern.charAt(j))) { // (j == -1) first!
15                  i++; // process next character
16                  j++;
17              } else {
18                  j = next[j]; // go to next state
19              }
20          } while ((j < m) && (i < n));
21          if (j == m) {
22              return (i - m); // pattern found: index to position in searchString
23          } else {
24              return -1; // pattern not found
25          }
26      }
27  
28      private static int[] initNext(final String pattern) {
29          final int m = pattern.length();
30          final int[] next = new int[m];
31          int i = 0;
32          int j = -1;
33          next[0] = -1;
34          // special value! (-1 = no reference to a following state)
35          do {
36              if ((j == -1) || (pattern.charAt(i) == pattern.charAt(j))) {
37                  // (j == -1) must be first operand!
38                  i++;
39                  j++;
40                  next[i] = j;
41              } else {
42                  j = next[j];
43              }
44          } while (i < (m - 1));
45          return next;
46      }
47  }