[LintCode] strStr

  /**
     * 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) {
        //write your code here
        if(target == null)
            return -1;
        if(target.length() == 0)
            return 0;
        String str = target+'$'+source;
        int[] e = z(str);
        for(int i = 0 ; i < e.length; i++) {
            if(e[i] == target.length()) {
                return i - target.length() - 1;
            }
        }
        return -1;
    }
    public int[] z (String s) {
        int[] z = new int[s.length()];
        int l = 0;
        int r = 0;
        for(int i = 1; i < z.length; i++) {
            if(i <= r)
                z[i] = Math.min(r-i+1,z[i-l]);
            while(i + z[i] < z.length && s.charAt(z[i]) == s.charAt(i+z[i]))
                z[i]++;
            if(i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }