My code:
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null)
return -1;
if (needle.length() == 0)
return 0;
int[] next = getNext(needle);
int j = 0;
int i = 0;
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
else
j = next[j];
}
if (j == needle.length())
return i - j;
else
return -1;
}
private int[] getNext(String needle) {
int[] next = new int[needle.length()];
int k = -1;
int j = 0;
next[0] = -1;
while (j < needle.length() - 1) {
if (k == -1 || needle.charAt(k) == needle.charAt(j)) {
k++;
j++;
if (needle.charAt(k) != needle.charAt(j))
next[j] = k;
else
next[j] = next[k];
}
else
k = next[k];
}
return next;
}
public static void main (String[] args) {
Solution test = new Solution();
System.out.println(test.strStr("mississippi", "a"));
}
}
My test result:
這道題目要求是用KMP算法來做的。具體KMP算法是什么東西及老，就看這篇博客吧品追。
講的太詳細(xì)了。
http://blog.csdn.net/v_july_v/article/details/7041827
KMP 算法的核心卒茬，或者是難點(diǎn)，就是構(gòu)造next[] 數(shù)組咖熟。
一旦next[] 數(shù)組構(gòu)造好了圃酵，主程序很好寫。
那么馍管， next[] 數(shù)組的難點(diǎn)是什么郭赐。關(guān)鍵在于理解。
next[j] 是什么意義呢确沸？
意義是捌锭， 在 [0, j - 1] 這個(gè)區(qū)域內(nèi)，string needle 的最大前綴后綴相等長度罗捎。
也就是說观谦， next[] 數(shù)組求解過程中，
是通過 next[j - 1] 來求 next[j]桨菜， 當(dāng)?shù)扔趈時(shí)豁状，此時(shí)要求的又是 next[j + 1]了。
所以倒得， j < needle.length() - 1
因?yàn)楫?dāng)j = needle.length() - 2 時(shí)泻红， 就可以求出 next[needle.length() - 1] 了。
然后還需要理解一些概念霞掺。
next[j] = 0; 是什么含義谊路。
代表在 [0, j - 1] 這段區(qū)域內(nèi)，string needle 沒有重復(fù)的前綴后綴菩彬，隨意缠劝，
直接拿 haystack[i] 與 needle[0] 進(jìn)行比較了。相當(dāng)于挤巡，在 i 處失配時(shí)剩彬，直接將字符串needle頭部直接移動到i處。重新進(jìn)行匹配矿卑。
那么 next[j] = -1 是什么含義呢喉恋？
代表， haystack[i] 也不等于 needle[0], 即，在i處失配時(shí)轻黑，甚至都不需要將needle頭部與i開始的字符串重新進(jìn)行匹配了糊肤，直接跳過i，和i + 1處開始的字符串進(jìn)行重新匹配氓鄙。
這就是改進(jìn)版的KMP馆揉，將next[] 優(yōu)化了。
而且求 next[] 數(shù)組時(shí)抖拦，
while (j < needle.length() - 1) {
if (k == -1 || needle.charAt(k) == needle.charAt(j)) {
k++;
j++;
if (needle.charAt(k) != needle.charAt(j))
next[j] = k;
else
next[j] = next[k];
}
else
k = next[k];
}
一開始我在想升酣，在needle和haystack匹配到很長時(shí)，如果此時(shí)失配态罪，那么k = next[k]噩茄，這時(shí)再次失配呢？沒關(guān)系复颈，那么就再次進(jìn)行循環(huán)绩聘。
因?yàn)樵谶@個(gè)過程中，j是不變化的耗啦，k是不斷往后倒退的凿菩。直到找到符合的情況。
這就是一種遞歸啊帜讲。用while體現(xiàn)出來的一種遞歸思想衅谷，更科學(xué)的應(yīng)該稱為，迭代似将？
還有就是優(yōu)化next的代碼会喝，多了這么一段。
if (needle.charAt(k) != needle.charAt(j))
next[j] = k;
else
next[j] = next[k];
我在想玩郊，在needle和haystack匹配到很長時(shí)，如果此時(shí)下一個(gè)繼續(xù)匹配了枉阵，但是檢測出译红，
needle.charAt(k) == needle.charAt(j)
那么我們需要執(zhí)行這個(gè)操作，
next[j] = next[k];
那我們一定可以保證兴溜，
needle.charAt(k) != needle.charAt(next[j]) 嗎侦厚？
一定可以保證的。
因?yàn)槲覀兪菑? 開始 往后填充next[]的拙徽，我們一步步往前走刨沦，保證每一步的
needle.charAt(k) != needle.charAt(next[j])
所以一直遞歸到后面，是可以保證的膘怕。
很像是那個(gè) 科學(xué)證明法想诅，從1開始證明，到后面，都理所當(dāng)然了来破。
KMP就總結(jié)到這里了篮灼。
**
總結(jié)： String， KMP
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int strStr(String haystack, String needle) {
String s = haystack;
String p = needle;
if (s == null || p == null) {
return -1;
}
else if (p.length() == 0) {
return 0;
}
int[] next = getNext(p);
int i = 0;
int j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
}
else {
if (j == 0) {
i++;
}
else {
j = next[j];
}
}
}
if (j >= p.length()) {
return i - p.length();
}
else {
return -1;
}
}
private int[] getNext(String p) {
int[] dp = new int[p.length()];
dp[0] = -1;
int k = -1;
int j = 0;
while (j < dp.length - 1) {
if (k == -1 || p.charAt(k) == p.charAt(j)) {
k++;
j++;
dp[j] = k;
}
else {
k = dp[k];
}
}
return dp;
}
}
又把 KMP算法看了一遍徘禁，希望這次別再忘了诅诱。
其實(shí)就是 DP
Anyway, Good luck, Richardo! -- 09/20/2016
