strStr

leetcode 28.

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Solution. This problem is asking to implement source.indexOf(target) method. A brilliant solution is from here.

public int strStr(String source, String target) {
    for (int i = 0; true; i++) {
        for (int j = 0; true; j++) {
            if (j == target.length()) {
                return i;
            }
            if (i + j == source.length()) {
                return -1;
            }
            if (source.charAt(i + j) != target.charAt(j)) {
                break;
            }
        }
    }
}

Another effective solution is KMP:

public static int[] getNext(String str) {
    int[] next = new int[str.length()];
    int i = 0, j = 1;
    while (j < str.length() - 1) {
        if (str.charAt(i) == str.charAt(j)) {
            i++;
            j++;
            next[j] = i;
        }
        else if (i != 0) {
            i = 0;
        }
        else {
            j++;
        }
    }
    return next;
}

public static int strStr(String src, String pattern) {
    int[] next = getNext(pattern);
    int i = 0, j = 0;
    while (i < src.length() && j < pattern.length()) {
        if (src.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        }
        else if (j != 0) {
            j = next[j];
        }
        else {
            i++;
        }
    }
    return j == pattern.length() ? i - pattern.length() : -1;
}

Check my code on github.