Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
就是find a string in another string. Using KMP algorithm.
A:
就是KMP算法的实现。
public class Solution { public String strStr(String haystack, String needle) { // use KMP algorithm String T = haystack; String P = needle; int n = T.length(); int m = P.length(); // deal with the case that some are empty if(m ==0){ return T; } if(n == 0){ return null; } int[] pi = computePrefix(P); int q = -1; // q is the status of current match for (int i = 0; i < n; i++) { while (q >= 0 && P.charAt(q + 1) != T.charAt(i)) { q = pi[q]; } // not either q == -1 , or P[q+1] == T[i] if (P.charAt(q + 1) == T.charAt(i)) { q++; } if (q == m - 1) {// we reach the last match of string P return T.substring(i - m + 1); // return only the first occurence } } return null; } private int[] computePrefix(String P) { int m = P.length(); int[] pi = new int[m]; pi[0] = -1; // meaning that we do not find match at all int k = -1; // k is the number of chars that matched for (int i = 1; i < m; i++) { while (k >= 0 && P.charAt(k + 1) != P.charAt(i)) { k = pi[k]; } if (P.charAt(k + 1) == P.charAt(i)) { k++; } pi[i] = k; } return pi; } }----------------------3 rd pass--------------------------------------
Mistakes when writing KMP.
1 : 下面的这行, 错写成了 i<= n-m . 哎, 还是对k 的意思不是很清晰明白阿
for (int i = 0; i < n; i++) {
2: when computing prefix function.
if (P.charAt(k + 1) == P.charAt(i)) {错写成了。
if (P.charAt( pi[k] + 1) == P.charAt(i)) {
Mistakes:
1 : 当输入都为empty的时候, 输出也要为empty, 也就是说, 在"" 中,还是可以找到"" 的。
2: 当输入是( "a", "" ) 输出希望的,也是"a" ----------start of the finding string.
-----------第二遍------------
1: 所有的k, q , 刚开始的时候,都要设为-1. 而不是CLRS上的0。 表明什么都没有match上
2: 返回的时候,要注意,是返回的 s.substring ( i-m+1)
Learned:
No comments:
Post a Comment