strStr

Problem

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1.

Challenge

O(n^2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Code - Java

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;
        char[] s = source.toCharArray();
        char[] t = target.toCharArray();
        if (t.length == 0) return 0;
        int i, j;
        for (i = 0; i < s.length; i++) {
            for (j = 0; j < t.length; j++) {
                if (i + j >= s.length || s[i + j] != t[j]) {
                    break;
                }
            }
            if (j == t.length) return i;
        }
        return -1;
    }
}