28. Implement strStr()
459. Repeated Substring Pattern
1392. Longest Happy Prefix (KMP求next數(shù)組)
P3375 【模板】KMP字符串匹配
給定模式串 pattern 和目標串 text挎塌，求模式串在目標串中的所有出現(xiàn)位置
暴力算法 O(mn)
the brute force method is to match all substrings in text with the pattern string
if len(p) = m, len(text) = n, it will O(mn) time in the worst case
what is the worst case? pattern is "aaaaa" and text is "aaaaaaaaaaaaaaaa",
in this case until we reach the last char of pattern can we know they have a match-
為什么暴力算法可以加速寞冯，有哪些浪費
相鄰的兩次匹配有許多重復(fù)比較猛们，so many repeated comparisons
如果我們知道藍色T的后綴和紅T的前綴相同
當(dāng)藍T的后綴匹配了S串的時候，紅T的前綴也可以匹配S串
紅T匹配時就可以直接從黃色箭頭位置開始
kmp1
kmp2 -
KMP partial match table
pm[i] 表示 字符串長度為i+1的前綴里（除本身外）楞陷，最長相等前后綴的長度
kmp3
next[i] means if we reach i in pattern string and find a mismatch, the position of pattern string we should move back so as to compare with the corresponding text char
kmp4
在2的位置發(fā)現(xiàn)mismatch, 將pattern的2位置對齊這個mismatch的位置
因為什么呢，在mismatch之前的部分营曼，最長相等前后綴的長度為2
that means in previous successful match, pattern's 2 位前綴和其 2 為后綴相同（綠色部分）蛾派，所以前兩個不用再比較，compare from the third number（index is 2）
kmp5
失配往毡，模式串跳next
如何快速計算next - 動態(tài)規(guī)劃
KMP模板蒙揣，雖然沒有通過洛谷的所有testcase，但模板是對的
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class LuoP3375 {
public static void main(String[] args) {
char[] pattern = new char[]{'A', 'B', 'A'};
char[] text = new char[]{'A', 'B', 'A', 'B', 'A', 'B', 'C'};
// Scanner in = new Scanner(System.in);
// String s1 = in.nextLine();
// String s2 = in.nextLine();
// in.close();
// char[] text = s1.toCharArray();
// char[] pattern = s2.toCharArray();
int[] next = getNext(pattern);
List<Integer> res = kmp(pattern, text, next);
for (int i = 0; i < res.size(); i++) {
System.out.println(res.get(i) + 1);
}
for (int i = 1; i < next.length; i++) {
System.out.print(next[i] + " ");
}
}
public static List<Integer> kmp(char[] pattern, char[] text, int[] next) {
int i = 0, j = 0;
int len1 = text.length, len2 = pattern.length;
List<Integer> res = new ArrayList<>();
while (i < len1 && j < len2) {
if (j == -1 || text[i] == pattern[j]) {
i++; j++;
} else {
j = next[j];
}
if (j == len2) {
res.add(i - len2);
j = next[j];
}
}
return res;
}
public static int[] getNext(char[] pattern) {
int[] next = new int[pattern.length + 1];
next[0] = -1;
int j = -1, i = 0;
while (i < pattern.length) {
if (j == -1 || pattern[i] == pattern[j]) {
next[++i] = ++j;
} else {
j = next[j];
}
}
return next;
}
}
