https://www.youtube.com/watch?v=GTJr8OvyEVQ
public class Solution {
public int strStr(String haystack, String needle) {
if(haystack.length() < needle.length()) return -1;
if(needle.length() == 0) return 0;
int[] next = getNext(needle);
int q = 0; // number of chars matched in pattern
for(int i = 0; i < haystack.length(); i++){
while(q > 0 && needle.charAt(q) != haystack.charAt(i)){
q = next[q - 1];
}
if(needle.charAt(q) == haystack.charAt(i)){
q ++;
}
if(q == needle.length()){
return i - needle.length() + 1;
}
}
return -1;
}
private int[] getNext(String pattern){
int M = pattern.length();
int[] next = new int[M];
int k = 0; // number of chars matched in pattern
for(int i = 1; i < M; i++){
while(k > 0 && pattern.charAt(k) != pattern.charAt(i)){
k = next[k - 1];
}
if(pattern.charAt(k) == pattern.charAt(i)){
k ++;
}
next[i] = k;
}
return next;
}
}
next[] 里的 k = 正确 match 的长度
next[] 中，每个位置的数字是由 k 赋值的，代表“如果下一个字符串挂了，在我这个位置截止的字符串正确 match 的长度是多少”
于是这个 getNext() 函数就很好解释了。 next[] 的大小等于 pattern 长度，k 初始值为 0.
next[0] = 0 因为 substring 长度如果只为 1 的话，前面没东西和它匹配。
于是开始一个 while 循环，迭代寻找如果当前字符串挂了，我们目前的最长 suffix 到底多长，有可能会跳很多步。这个写法有点类似于 disjoint set 里面 weighted union-find 的 path compression 实现，就是一个 while 循环迭代赋值 index 一直到正确的 / base case 为止。 k > 0 这个条件很重要，不然如果在第一个字符串挂了之后，会去找 next[-1] 就越界了。
每次我们在 index k 上挂的时候，是去找 next[k - 1] 的 k 值是什么。原因是 length 与 index 间有 1 的 offset ，我们去看 index = k 的位置其实是在考虑要不要把 length 设成 k + 1.
此后如果当前字符串匹配，就把 k + 1，赋值到当前 next[i] 上。赋值之后就不会再改了
理解
- next[0] =0 因为substring长度如果只为1的话, 前面没有可以匹配的
- 上图中 j=5, i=8; s[5] 与 s[8]不匹配, 此时去看arr[4]的值为2, 回溯到上一个有可能可以match的地方比如s.substring(0,2) 是"aa". 因为s.subtring(3,5)与s.subtring(6,8)保证匹配, s.substring(3,5)与s.subtring(0, 2)保证匹配, 所以s.substring(0,2)与s.substring(6,8) "aa" 匹配, 继续检查s[2]和s[8]是否匹配. 发现不匹配. 继续回溯,
- 此时 j=2, i=8, 去看arr[1]的值是1, 利用上一步结论, s.substring(0,1)是可以与s.substring(7,8)匹配, 检查是否s[1]与s[8]匹配, 结果匹配, arr[8] = arr[1]+1;
- 如果匹配, 那么i j自增1
public class Solution { public int strStr(String haystack, String needle) { if(haystack.length() < needle.length()) return -1; if(needle.length() == 0) return 0; int[] arr = getNext(needle); int i=0;int j=0; for(;i<haystack.length();i++){ while(j>0 && haystack.charAt(i)!=needle.charAt(j)) j = arr[j-1]; if(haystack.charAt(i)==needle.charAt(j)){ j++; } if(j==needle.length()) return i-needle.length()+1; } return -1; } public int[] getNext(String needle){ int[] arr = new int[needle.length()]; arr[0] =0;int j = 0; int i=1; for(;i<needle.length();i++){ while(j>0 && needle.charAt(i)!=needle.charAt(j)) j = arr[j-1]; if(needle.charAt(i)==needle.charAt(j)) j++; arr[i] = j; } return arr; } }
(G) 面经题http://www.1point3acres.com/bbs/thread-199776-1-1.html
给两个字符串，找到第二个在第一个中第一次出现的位置（自己写string.indexOf这个函数吧），followup1，找一个字符串中period的字符段，followup2，找到period次数最少的，例如abababab，ab出现了4次，abab出现了2次，返回2
Shortest Palindrome
先用two pointers，将原string翻转，two pointers找最长公共suffix/prefix
非常巧妙的思路, str+"#"+str.reverse()来构造string, 打kmp算法的表, 表尾end值代表palindrome的长度
https://leetcode.com/problems/shortest-palindrome/#/solutions
KMP table:
c a t a c b # b c a t a c
0 0 0 0 1 0 0 0 1 2 3 4 5
public class Solution {
public String shortestPalindrome(String s) {
StringBuilder sb = new StringBuilder(s);
sb = new StringBuilder(s+"#"+sb.reverse().toString());
System.out.println(sb.toString());
int[] table = new int[sb.length()];
int j=0; int i=1;
for(;i<table.length;i++){
if(sb.charAt(i)==sb.charAt(j)){
table[i] = table[i-1]+1;
j++;
}
else{
j = table[i-1];
while(j>0&&sb.charAt(i)!=sb.charAt(j)){
j=table[j-1];
}
if(sb.charAt(i)==sb.charAt(j)){
j++;
}
table[i] = j;
}
}
int val = table[table.length-1];
System.out.println(Arrays.toString(table));
StringBuilder ans = new StringBuilder(s.substring(val)).reverse();
return ans.toString()+s;
}
}