KMP

prefix與suffix

prefix 中文為前綴，英文字根。
suffix 中文為後綴，英文字尾。

想像一下，學習英文，有一些字首字根，就可以猜出字母的意思，比如pre有事前、預備。
英文字尾為tion為名詞。

前綴

但這邊的前綴是以下這樣的，不包含字尾。
字串 = abab
abab → a
abab → ab
abab → aba

後綴

後綴是以下這樣的，不包含字首。
字串 = abab
abab → b
abab → ab
abab → bab

共同前綴後綴

共同前綴後綴，意思是前綴與後綴中都擁有相同字串。 abab前綴與後綴都擁有相同的字串為:ab

next陣列

a只有一個字母，前綴不包含字尾，後綴不包含字首。所以共同前後綴為0。
ab，沒有共同前後綴，所以為0。

aba:
前綴:a ab
後綴:a ba
共同前後綴為a
a字串長度為1，共同前後綴長度為1。

abab:
前綴:a ab aba
後綴:b ab bab
共同「最長」前後綴為ab，字串長度為2。

pattern字串	a	b	a	b
共同前後綴長度	0	0	1	2
對映的字串	a	ab	aba	abab

next陣列程式碼步驟

預設只有一個字元，不會有共同前後綴。所以next[0] = 0

j是指向「前」綴，i是指向「後」綴。
ab，j指向a，i指向b，二個字母不相同，沒有共同前後綴，把j指向的索引0，塞入next陣列。

next[i=1] = 0

i++，往右移動i=2。
j指向a，i指向a，二個字母相同

j++，j往右移動，j=1。
j指向索引1，把j指向的索引1，塞入next陣列。

next[i=2] = 1

i++，往右移動i=3。

j指向b，i指向b，二個字母相同。

j++，j往右移動，j=2。
j指向索引2，把j指向的索引2，塞入next陣列。

next[i=3] = 2

i++，往右移動i=4。
j指向a，i指向c，二個字母不相同。

j = 2，套用以下的公式，找出next[1] = 0，j移動到索引0的位置。

j = next[j - 1]
j = next[2 - 1]

j指向a，i指向c，二個字母仍是不相同，把j指向的索引0，塞入next陣列。

next[i=4] = 0

多次回推的next陣列範例

pattern字串 = abababc

對映的next陣列:

索引	0	1	2	3	4	5	6
字串	a	b	a	b	a	b	c
next陣列	0	0	1	2	3	4	?

目前i指向索引6，j指向索引4。
i指向c，j指向a，二個字母不相同。
j = 4，套用以下的公式，找出next[3] = 2。

j = next[j - 1]
j = next[4 - 1]

j移動到索引2的位置。

目前i指向索引6，j指向索引2。
i指向c，j指向a，二個字母不相同。
j = 2，套用以下的公式，找出next[1] = 0。

j = next[j - 1]
j = next[2 - 1]

j移動到索引0。
i指向c，j指向a，二個字母不相同。
j已經沒辦法再往左移動，往左移動就變-1。
next[i=6] = 0，0是j的索引。

索引	0	1	2	3	4	5	6
字串	a	b	a	b	a	b	c
next陣列	0	0	1	2	3	4	0

i指向c，j指向a，二個字母不相同，不會進到if。

next[i=6] = 0，0是j的索引。

將next陣列傳回。

getNext程式碼:

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
  public static int[] getNext(String pattern) {
    int[] next = new int[pattern.length()];
    // j指向前綴，預設為0
    int j = 0;
    // next[0]，固定都是0，因為沒有前綴後綴
    next[0] = 0;
    // i指向後綴，固定由1開始
    for (int i = 1; i < pattern.length(); i++) {
      // 判斷索引j與i指向的值是否相等，不相等就找next[j-1]
      // j=0已經沒辦法再往左移動變-1，就離開while迴圈
      // j>0才能進入迴圈
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
        j = next[j - 1];
      }
      // j 替換成next[j-1]，比對後可以配對到索引i指向的值
      if (pattern.charAt(i) == pattern.charAt(j)) {
        // j就往右邊移動一格
        j++;
      }
      // 如果沒有比對到
      // 或是有比對到
      // next[i索引] 放置j的索引
      next[i] = j;
    }
    return next;
  }

完整程式碼

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
public class Kmp {
  public static void main(String[] args) {
    String str = "aabaa";
    String pattern = "aaa";
    int[] next = getNext(pattern);
    System.out.println(Arrays.toString(next));
    int i = 0, j = 0 ;
    int findIndex = -1;
    for(;i < str.length(); i++) {
      while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
        j = next[j-1];
      }
      if (str.charAt(i) == pattern.charAt(j)) {
        j++;
      }
      if (j == pattern.length()) {
        findIndex = i - j + 1;
        break;
      }
    }
    if (findIndex != -1) {
      System.out.println("find index = " + findIndex);
    } else {
      System.out.println("can not find index.");
    }
  }
  public static int[] getNext(String pattern) {
    int[] next = new int[pattern.length()];
    // j指向前綴，預設為0
    int j = 0;
    // next[0]，固定都是0，因為沒有前綴後綴
    next[0] = 0;
    // i指向後綴，固定由1開始
    for (int i = 1; i < pattern.length(); i++) {
      // 判斷索引j與i指向的值是否相等，不相等就找next[j-1]
      // j=0已經沒辦法再往左移動，就離開while迴圈
      // j>0才能進入迴圈
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
        j = next[j - 1];
      }
      // j 替換成next[j-1]，比對後可以配對到索引i指向的值
      if (pattern.charAt(i) == pattern.charAt(j)) {
        // j就往右邊移動一格
        j++;
      }
      // 如果沒有比對到
      // 或是有比對到
      // next[i索引] 放置j的索引
      next[i] = j;
    }
    return next;
  }
}

KMP

KMP