2015年7月2日星期四

strStr KMP solution Java

KMP :
prefix array to find prefix and suffix.
use for - while loop .

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target) {
        if(source==null || target==null)
            return -1;
        if(target.length()==0)
            return 0;
        int[] prefix= new int[target.length()];
        int k=0;
        for(int i=1;i<target.length();i++){
            while(k>1 && target.charAt(k)!= target.charAt(i))
                k=prefix[k-1];
            if(target.charAt(i)==target.charAt(k))
                k++;
            prefix[i]=k;
        }
        k=0;
        for(int i=0;i<source.length();i++){
             while( k>1 && source.charAt(i)!= target.charAt(k))
                k=prefix[k-1];
            if(target.charAt(k) ==source.charAt(i))
                k++;
            if(k== target.length())
                return i-k+1;
        }
        return -1;
    }
}

没有评论:

发表评论