KMP
刷题路线以及 KMP 详解 ：代码随想录
什么是 KMP 算法?
KMP 是以 3 位发明者名字的首字母命名的，常用来字符串匹配上。如：判断 s1 是不是 s2 的子串，KMP 算法将解决此问题的时间复杂度从 O(m*n) 降低到了 O(n)
它的思想是当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
如：文本串：aabaabaaf，模式串：aabaaf，判断 aabaaf 是否为 aabaabaaf 的子串
aabaabaaf
aabaaf
当在文本串下标 i = 5 处发现 b 和 f 不匹配时，模式串没有从文本串下标 i = 1 和 i = 2 开始从头比较，
aabaabaaf
. aabaaf
. . aabaaf
而是让下标 i 不回退，改变模式串下次比较的下标，在 aabaaf 的 f处 匹配失败，但是我们发现 f 前边的 aa (. . . aaf 和 开头的 aa. . . .) 相同 而因为已经匹配到 f 说明 f 前的 aabaa(aabaaf) 一定与 文本串（aabaabaaf）的 aabaa 已经完全匹配，那么文本串（aabaabaaf）发生匹配失败的前的 aa 一定在 模式串（aabaaf）的前缀出现。此时就可以直接去比较两个 aa 后边的字符就可以了。
aabaabaaf
. . . aabaaf
next 数组
数组next[i] 保存模式串[0, i] 区间子串的最长相同前后缀的长度，在匹配失败时，用来找到下次应该匹配的位置。最大相等前后缀的长度作为下标刚好是前缀尾部后一个位置，刚好作为匹配失败模式串指针回退的位置。
题录
28. 实现 strStr()
Leetcode 链接
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：
输入：haystack = “”, needle = “”
输出：0
题解： 我们称 haystack = “hello”, needle = “ll” 中前者为文本串，后者为模式串
方式一：暴力解，第一层循环遍历文本串表示相同子串开始位置，第二层循环遍历模式串
class Solution {
public int strStr(String haystack, String needle) {
int hLen = haystack.length();
int nLen = needle.length();
// 模式串为空，返回0
if (nLen == 0) return 0;
// i 表示文本串该位置作为匹配的起始位置，所以 循环到hLen - nLen 结束，因为再往后一个位置作为匹配的起始位置，文本串剩余位置不够模式串匹配
for (int i = 0; i <= hLen - nLen; i++) {
if (haystack.charAt(i) == needle.charAt(0)) {
// 文本串 i 下标位置和模式串0下标位置已经匹配上，从 i+1 位置开始向后匹配
int j = 1;
// j 指向模式串每轮匹配位置，则文本串每轮匹配位置为 i + j
while (j < nLen && haystack.charAt(i + j) == needle.charAt(j)) {
// 当前字符匹配，j 指向下轮要匹配的位置
j++;
}
// 如果已经匹配到最后一个位置，表示整个模式串匹配成功，返回本轮匹配的起始位置
if (j == nLen) return i;
}
}
// 没有匹配成功
return -1;
}
}
KMP解法：
class Solution {
public int strStr(String haystack, String needle) {
int hLen = haystack.length();
int nLen = needle.length();
if (nLen == 0) return 0;
// j 为模式串指针，表示接下来模式串比较的位置
int j = 0;
// 得到模式串对应的 next 数组
int[] next = getNext(needle);
// i 为文本串指针，表示接下来文本串比较的位置
// 这里循环与暴力解法结束位置不同需要注意，因为这里的 i 表示接下来文本串比较的位置，i 要走到头
for (int i = 0; i < hLen; i++) {
// 如果不相等，j 回退，而 i不动
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
// j 回退到[0，j)子串的最大相等前后缀的前缀尾后一个位置，如果没有相等的前后缀直接回到0 下标
j = next[j - 1];
}
// 如果相等 j++，循环结束 i也++，表示接下来比较的位置
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
// 模式串指针 j 已经走到最后，成功匹配
if (j == nLen) return i - nLen + 1;
}
}
return -1;
}
public int[] getNext(String s) {
int len = s.length();
// 1. 初始化
int[] next = new int[len];
int j = 0; // 前缀指针 j=0， 后缀指针 i=1
// j 代表接下来应该比较的前缀，同时代表这最大相等前后缀长度；i 代表接下来应该比较的后缀
for (int i = 1; i < len; i ++) {
// i 接下来需要比较的后缀，同时也表示 next 数组本轮填充位置
// 不相等时回退
while (j > 0 && s.charAt(i) != s.charAt(j)) {
// j 回退到[0，j)子串的最大相等前后缀的前缀尾后一个位置，如果没有相等的前后缀直接回到0 下标
j = next[j - 1];
}
// 相等时 j++，表示最大相等前后缀长度+1，同时指向下一次应该比较的前缀位置
if (s.charAt(i) == s.charAt(j)) {
j++;
}
// next数组 i 下标填充 [0, i] 子串的最大相等前后缀长度
next[i] = j;
}
return next;
}
}
459. 重复的子字符串
Leetcode 链接
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s = “aba”
输出: false
示例 3:
输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
题解：
暴力解法：以前 i 个字符作为子串是否能被重构，第一层循环遍历所有 i 的可能，第二次循环使用双指针判断能否被重构
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
// i 表示子串长度，从 1 到最大 len/2
for (int i = 1; i <= len / 2; i++) {
// 如果子串长度为 len 的因数，表示可能被 [0,i) 区间子串重构
if (len % i == 0) {
int j = 0;
// 双指针 j 和 j + i 位置逐个比较
for (; j < len - i; j ++) {
if(s.charAt(j) != s.charAt(j + i)) {
// 一旦必相等，表示不能被 [0,i) 区间子串重构
break;
}
}
// 如果是因为越界结束循环，表示可以被重构
if (j + i == len) return true;
}
}
return false;
}
巧解：
举个栗子： 如果能被子串重构，那么原字符串经过循环移位后一定能等于原字符串
abab
. baba
. . abab
abababab 也就是说满足原字符串是两个原字符串拼接再一起去头去尾 bababa 的子串
public boolean repeatedSubstringPattern(String s) {
String str = s + s;
return str.substring(1, str.length()-1).contains(s);
}
KMP解法:
举个栗子：
s = “abcabcabcabc” 对应 next 数组为：000 123 456 789，s.length() = 12 = 9(next 数组最后一位) + 3(重构子串长度)，3 是 s长度的因数，所以 s 能被子串重构
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
int[] next = new int[len];
// 前缀指针 j
int j = 0;
// 填充 next 数组
for (int i = 1; i < len; 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;
}
// 子串长度不能等于 s 长度
if (next[len - 1] == 0) return false;
// 子串长度：len - next[len - 1]
return (len % (len - next[len - 1]) == 0);
}
}