28. Find the Index of the First Occurrence in a String

LeetCode
,

Sliding Window / BF (my solution)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int strStr(String haystack, String needle) {
        int pos = 0;
        int n = haystack.length();
        int m = needle.length();
        while(pos <= n - m) {
            String sub = haystack.substring(pos, pos + m);
            if (needle.equals(sub)) return pos;
            pos++;
        }
        return -1;
    }
}

Remarks:

  1. Outer layer runs $n - m + 1$, inner layer runs $m$ (for comparing strings str1.equals(str2)).
  2. Worst TC: $O(nm)$, SC: $O(m)$

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;

        // build the next array
        int[] next = buildNext(needle);

        int i = 0; // haystack pointer
        int j = 0; // needle pointer

        while (i < n) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j]; // go back needle pointer
            }

            if (j == m) return i - j; // matched
        }

        return -1;
    }

    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1; //  default -1

        int j = 0; // current char
        int k = -1; // prefix pointer

        while (j < m - 1) {
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }

        return next;
    }
}