Algorithms/KMP.java at master · xzysolitaire/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package CrackingtheCodingInterview;

public class KMP {

  public static int getMatch(String P, String T) {
    int kmp[] = new int[P.length()];
    kmp[0] = -1;
    for (int i = 1; i < kmp.length; i++) {
      if (kmp[i - 1] != -1) {
        if (P.charAt(i) == P.charAt(kmp[i - 1] + 1)) {
          kmp[i] = kmp[i - 1] + 1;
        } else {
          kmp[i] = -1;
        }
      } else {
        if (P.charAt(i) == P.charAt(0)) {
          kmp[i] = 0;
        } else {
          kmp[i] = -1;
        }
      }
    }

    int t_index = 0, p_index = 0;
    while (t_index < T.length() && p_index < P.length()) {
      if (P.charAt(p_index) == T.charAt(t_index)) {
        p_index ++;
        t_index ++;
      } else {
        if (p_index == 0) {
          t_index++;
        } else if (kmp[p_index - 1] == -1) {
          p_index = 0;
        } else {
          p_index = kmp[p_index - 1] + 1;
        }
      }

      if (p_index == P.length()) {
        return t_index - P.length();
      }
    }

    return -1;
  }

  public static void main(String[] args) {
     String P = "annanna";
     String T = "annbcdanacadsannannabnna";
     System.out.println(getMatch(P, T));
  }

}