28. Implement strStr()
459. Repeated Substring Pattern
1392. Longest Happy Prefix (KMP求next数组)
P3375 【模板】KMP字符串匹配
给定模式串 pattern 和目标串 text，求模式串在目标串中的所有出现位置
暴力算法 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-
为什么暴力算法可以加速，有哪些浪费
相邻的两次匹配有许多重复比较，so many repeated comparisons
如果我们知道蓝色T的后缀和红T的前缀相同
当蓝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的位置发现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 - 动态规划
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;
}
}
