关于kmp的原理可以看左神或者卡神的视频讲解，我这边的kmp都是以next数组表示模式串的最长公共前后缀做题的，如下：
// pattern:ababf
// next[]:00120
static void prefix(int[] next,String pattern){
int j = 0;
for(int i=1;i<next.length;i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
next[i] = j;
}
}
}
题一.28. 找出字符串中第一个匹配项的下标
- 解题思路：这个就是最常规的kmp用法，用next数组去判断什么时候匹配字符的长度j等于模式串的长度，说明匹配成功了。
class Solution {
// KMP 算法
// s: 原串(string) p: 匹配串(pattern)
public int strStr(String s, String p) {
int[] next = new int[p.length()];
prefix(next,p);
int j = 0;
for(int i=0;i<s.length();i++){
while(j>0&&s.charAt(i)!=p.charAt(j)){
j = next[j-1];
}
if(s.charAt(i)==p.charAt(j)){
j++;
if(j==p.length()){
return i-p.length()+1;
}
}
}
return -1;
}
void prefix(int[] next,String pattern){
int j = 0;
for(int i=1;i<next.length;i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
next[i] = j;
}
}
}
}
题二：796. 旋转字符串
- 解题思路：把原串S变成S+S，然后用kmp算法快速匹配和S是否有重合的子串，比上题多了一个把S串变成2倍的思路。
class Solution {
public boolean rotateString(String s, String goal) {
if(s.length()!=goal.length()) return false;
String s2 = s + s;
int[] next = new int[goal.length()];
prefix(next,goal);
int j=0;
for(int i=1;i<s2.length();i++){
while(j>0&&s2.charAt(i)!=goal.charAt(j)){
j = next[j-1];
}
if(s2.charAt(i)==goal.charAt(j)){
j++;
if(j==goal.length()){
return true;
}
}
}
return false;
}
void prefix(int[] next,String pattern){
int j = 0;
for(int i=1;i<pattern.length();i++){
while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
j = next[j-1];
}
if(pattern.charAt(i)==pattern.charAt(j)){
j++;
next[i] = j;
}
}
}
}
题三：214. 最短回文串
- 这题相对来说比较难一点，主要是去思考构造一个最短的回文串和原串做一些啥处理后的next数组的关系：
// 拿一个abacd举一个例子
// s = dc+ (aba)cd
//所以其实就是去找到原串中回文的部分，保留不变，
//然后把后续的段逆转加到前面。转化为求最长回文子串的问题，
//这个当然可以用其他方式来做，比如中心扩散法等等（leetcode也有这道题），但是有不一样的地方，他要求只能在s前加，所以最长回文必须也是从0开始的。
//这边用kmp的思路是把abacd变成abacd#dcaba
//然后求这个串的next数组可以求出最长公共前后缀的长度是3(aba)
//这边有一个注意点就是一定要在中间加#，不然aaaaaa求出来长度就超过了s了。
class Solution {
public String shortestPalindrome(String s) {
if(s.length()==0) return "";
String s2 = s + "#" + new StringBuffer(s).reverse().toString();
int[] next = new int[s2.length()];
next[0] = 0;
int j = 0;
for(int i=1;i<s2.length();i++){
while(j>0&&s2.charAt(i)!=s2.charAt(j)){
j = next[j-1];
}
if(s2.charAt(i)==s2.charAt(j)){
j++;
next[i] = j;
}
}
int index= next[s2.length()-1];
return new StringBuffer(s.substring(index)).reverse().toString()+s;
}
}
题四：459. 重复的子字符串
- 思路，用kmp的话就是写出next数组，判断next数组的长度是否是原串长度剪去公共前后缀的整数倍数。
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = new int[s.length()];
int j = 0;
for(int i=1;i<s.length();i++){
while(j>0&&s.charAt(i)!=s.charAt(j)){
j = next[j-1];
}
if(s.charAt(i)==s.charAt(j)){
j++;
next[i] = j;
}
}
int len = s.length();
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
}
题5:1392. 最长快乐前缀
- 就是next数组，没啥好说的
class Solution {
public String longestPrefix(String s) {
int[] next = new int[s.length()];
int j = 0;
for(int i=1;i<s.length();i++){
while(j>0&&s.charAt(i)!=s.charAt(j)){
j = next[j-1];
}
if(s.charAt(i)==s.charAt(j)){
j++;
next[i] = j;
}
}
return s.substring(0,next[s.length()-1]);
}
}
