NC+LC：KMP算法
什么是KMP算法？
Knuth-Morris-Pratt 算法，简称 KMP算法，由 Donald Knuth、James H. Morris和 Vaughan Pratt 三人于 1977年联合发表。
KMP算法主要应用于字符串匹配，通过一个前缀表记录模式串与主串不匹配时，模式串应该从哪里开始重新匹配，而不用每次都从头开始匹配。
理解：如要在文本串aabaabaafa中查找是否存在模式串aabaaf，当遇到第六个字符时匹配失败，这时可以求出第六个字符前的字符串aabaa的最长公共前后缀为aa，匹配失败的位置出现在最长公共后缀的后一位，那么这时就可以从最长公共前缀的后一位开始继续与主串往后进行匹配，不用从头开始。
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串，求模式串aabaaf的前缀表如下：
如aa的前缀为a，后缀为a，则最长公共前后缀为a；aab的前缀有a,aa，后缀有ab,b，则没有公共前后缀；aabaa的前缀有a,aa,aab,aaba，后缀有abaa,baa,aa,a，最长公共部分为aa。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 子串 | a | aa | aab | aaba | aabaa | aabaaf |
| 最长公共前后缀长度 | 0 | 1 | 0 | 1 | 2 | 0 |
LC 28.实现strStr()
题目描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
示例：
输入：haystack = "hello", needle = "ll" 输出：2
思路
参考资料：【代码随想录】中的相关介绍
next数组其实就是前缀表的值减一
实现代码
class Solution { //KMP算法
public int strStr(String haystack, String needle) {
if(needle == "" || needle.length() == 0){
return 0;
}
int nlen = needle.length();
int[] next = new int[nlen];
getNext(next, needle);
int j = -1;
for(int i = 0; i < haystack.length(); i++){
while(j >= 0 && haystack.charAt(i) != needle.charAt(j+1)){ //不匹配
j = next[j]; //将之前匹配的位置赋给j
}
if(haystack.charAt(i) == needle.charAt(j+1)){ //匹配就往后移动
j++;
}
if(j == nlen - 1){ //j指向了needle的末尾则匹配到了子串
return i - nlen + 1; //当前位置i减去needle的长度+1就为出现的第一个位置
}
}
return -1;
}
public void getNext(int[] next, String str){ //求next数组
int j = -1; //指针j指向前缀起始位置
next[0] = j;
for(int i = 1; i < str.length(); i++){ //i指向后缀起始位置，从1开始
while(j >= 0 && str.charAt(i) != str.charAt(j+1)){ //前后缀不相同就回退
j = next[j];
}
if(str.charAt(i) == str.charAt(j+1)){ //相同就移动
j++;
}
next[i] = j; //将j（前缀的长度）赋给next[i]
}
}
} LC 459.重复的子字符串
题目描述
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。
示例：
输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
思路
参考资料：【代码随想录】459.重复的自字符串
实现代码
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s == "" || s.length() == 0) {
return false;
}
int len = s.length();
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
// 构造 next 数组过程，j从0开始(空格)，i从2开始
for (int i = 2, j = 0; i <= len; i++) {
// 匹配不成功，j回到前一位置 next 数组所对应的值
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
// 匹配成功，j往后移
if (chars[i] == chars[j + 1]) j++;
// 更新 next 数组的值
next[i] = j;
}
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
} 
