29-算法打卡-字符串-KMP算法理论2-第二十九天

1、KMP算法前缀表计算逻辑

可以查看上一章节的前缀表概念以及逻辑，KMP算法基础理论[基础概念、前缀、后缀、最长公共前后缀、前缀表]

2、KMP算法前缀表使用

当模式串和文本串匹配失败的时候，前缀表会告诉我们下一次的匹配中，模式串应该跳到那个位置。
a、文本串和模式串指向的字符相等则继续向下移动
b、文本串和模式串指向的字符不相等则模式串向左移动到对应next数组的前一位对应的数值。
        如图中，模式串向左移动2位。

3、获取KMP算法前缀表

3.1 思路

a、初始化：两个指针i,j;  j即是指向前缀的末尾也表示子串的最长公共前后缀长度；i是指向后缀的末尾也是指向next数组待更新的位置； j=0; next[0]=j
b、前后缀相同：指针j向右移动
c、前后缀不同：指针j移动到next[j-1]的位置
d、更新next数组

3.2 代码实现

private void getNext(int[] next, String s) {int j = 0; // 初始化next[0] = 0;for (int i = 1; i < s.length(); i++) {while (j > 0 && s.charAt(j) != s.charAt(i))  j = next[j - 1]; if (s.charAt(j) == s.charAt(i)) j++;next[i] = j; }}