KMP详解

例题 28.找出字符串中第一个匹配项的下标

题解 28.找出字符串中第一个匹配项的下标
这个算法第一次听说，假设你不是oi的话就是在数据结构课上，但是鉴于部分中国大学计算机系老师毋庸置疑的 “水” 平和令人发指的语言表达能力，大部分学生都是迷迷糊糊的，下面我对这个算法进行下详细讲解，希望对大家有所帮助。

next数组

next数组是KMP算法核心，含义：所有p[1~j]的相等的前缀和后缀中长度的最大值
这里说明下细节，两个需要匹配的字符串数组下标建议从1开始因为后续j的值直接对应前j个字符，无需额外计算偏移量,比如模式串 p = “abcabx” 下标从1开始时，p[1]=’a’、p[2]=’b’…p[6]=’x’，next[5] 直接表示前5个字符abcab的最长匹配长度（值为 2），逻辑清晰。

如上图可以看出next数组的实际含义，第一个A没有匹配的0，第二个B同理，第三个A和第一个A匹配所以记位1，AB和前面的AB匹配长度位2所以记做2，C没有匹配的记做0，所以next[4] = 2。之后子串或者所谓模式串往后移动两个即可。
通过这个例子也可以看出KMP的优势就是，当匹配到不同字符的时候，由于已经知道前面匹配成功的字符信息，就可以利用信息避免暴力遍历方法中的回退操作。也就是上面指针步回退，那么算法的时间复杂度就是线性的了（从O(n*m)到O(n+m))!

计算 next 数组

for (int i = 2, j = 0; i <= m; i++) {
            while (j > 0 && p.charAt(i) != p.charAt(j + 1)) {
                j = next[j];
            }
            if (p.charAt(i) == p.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }

就按照上面的例子进行讲解说明：
数组 next 长度为 m + 1（m 是子串长度，这里 m = 5），所以 next 数组大小为 6。
循环变量 i 从 2 开始（因为子串第一个字符索引为 1，next[1] 固定为 0，从第二个字符，即索引 2 开始计算），j 初始化为 0。
第一次循环（i = 2，计算 next[2]）
比较 p.charAt(i)（i = 2，即子串中索引为 2 的字符 ‘B’）和 p.charAt(j + 1)（j = 0，所以是 p.charAt(1)，即字符 ‘A’）。
因为 ‘B’ != ‘A’，且 j = 0，不满足 j > 0，所以 while 循环不执行。
由于 p.charAt(i) != p.charAt(j + 1)，j 保持 0，所以 next[2] = j = 0。
第二次循环（i = 3，计算 next[3]）
比较 p.charAt(3)（字符 ‘A’）和 p.charAt(1)（字符 ‘A’）。
因为 ‘A’ == ‘A’，所以 j++，此时 j = 1。
然后 next[3] = j = 1。
第三次循环（i = 4，计算 next[4]）
比较 p.charAt(4)（字符 ‘B’）和 p.charAt(2)（字符 ‘B’）。
因为 ‘B’ == ‘B’，所以 j++，此时 j = 2。
然后 next[4] = j = 2（这与图片里子串 next 数组中对应位置的值为 2 一致）。
第四次循环（i = 5，计算 next[5]）
比较 p.charAt(5)（字符 ‘C’）和 p.charAt(3)（字符 ‘A’）。
因为 ‘C’ != ‘A’，且 j = 2 > 0，进入 while 循环，执行 j = next[j]，即 j = next[2] = 0。
再次比较 p.charAt(5)（’C’）和 p.charAt(1)（’A’），还是不相等，且 j = 0，while 循环结束。
由于 p.charAt(i) != p.charAt(j + 1)，j 保持 0，所以 next[5] = j = 0。

在主串中匹配模式串

for (int i = 1, j = 0; i <= n; i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j + 1)) {
                j = next[j];
            }
            if (s.charAt(i) == p.charAt(j + 1)) {
                j++;
            }
            if (j == m) {
                return i - m;//i-m+1,但是从1开始所以要-1
            }
        }

第 1 次循环：

// 1. 检查不匹配时的回溯（j=0，不满足j>0，while循环不执行）
while (j > 0 && s.charAt(1) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配判断：s[1]='A' == p[1]='A'（j+1=1），j自增为1
if (s.charAt(1) == p.charAt(j + 1)) {
    j++; 
}
// 3. 检查是否完全匹配：j=1 != 7，不返回
if (j == m) {
    return i - m;
}

第 2 次循环：

// 1. while循环：j=1>0，但s[2]='B' == p[2]='B'（j+1=2），循环不执行
while (j > 0 && s.charAt(2) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[2]='B' == p[2]='B'，j自增为2
if (s.charAt(2) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=2 != 7，不返回
if (j == m) {
    return i - m;
}

第 3 次循环：

// 1. while循环：j=2>0，但s[3]='A' == p[3]='A'（j+1=3），循环不执行
while (j > 0 && s.charAt(3) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[3]='A' == p[3]='A'，j自增为3
if (s.charAt(3) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=3 != 7，不返回
if (j == m) {
    return i - m;
}

第 4 次循环：

// 1. while循环：j=3>0，但s[4]='B' == p[4]='B'（j+1=4），循环不执行
while (j > 0 && s.charAt(4) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[4]='B' == p[4]='B'，j自增为4
if (s.charAt(4) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=4 != 7，不返回
if (j == m) {
    return i - m;
}

第 5 次循环：

// 1. while循环：j=4>0，且s[5]='A' != p[5]='C'（j+1=5），执行回溯
while (j > 0 && s.charAt(5) != p.charAt(j + 1)) {
    j = next[j]; // j = next[4] = 2（根据next数组取值）
}
// 2. 回溯后判断：s[5]='A' == p[3]='A'（j+1=3），j自增为3
if (s.charAt(5) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=3 != 7，不返回
if (j == m) {
    return i - m;
}

第 6 次循环：

// 1. while循环：j=3>0，但s[6]='B' == p[4]='B'（j+1=4），循环不执行
while (j > 0 && s.charAt(6) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[6]='B' == p[4]='B'，j自增为4
if (s.charAt(6) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=4 != 7，不返回
if (j == m) {
    return i - m;
}

第 7 次循环：

// 1. while循环：j=4>0，但s[7]='C' == p[5]='C'（j+1=5），循环不执行
while (j > 0 && s.charAt(7) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[7]='C' == p[5]='C'，j自增为5
if (s.charAt(7) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=5 != 7，不返回
if (j == m) {
    return i - m;
}

第 8 次循环：

// 1. while循环：j=5>0，但s[8]='A' == p[6]='A'（j+1=6），循环不执行
while (j > 0 && s.charAt(8) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[8]='A' == p[6]='A'，j自增为6
if (s.charAt(8) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=6 != 7，不返回
if (j == m) {
    return i - m;
}

第 9 次循环：

// 1. while循环：j=6>0，但s[9]='B' == p[7]='B'（j+1=7），循环不执行
while (j > 0 && s.charAt(9) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. 字符匹配：s[9]='B' == p[7]='B'，j自增为7
if (s.charAt(9) == p.charAt(j + 1)) {
    j++; 
}
// 3. 完全匹配检查：j=7 == m=7，返回i - m = 9 - 7 = 2
if (j == m) {
    return i - m;
}

最终结果：返回2（对应原主串”ABABABCABA”的起始下标，即从第 3 个字符开始匹配成功）