Implement strStr()

Q:
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: