LeetCode. 28. Implement strStr()

[Link] https://leetcode.com/problems/implement-strstr/

The prefix-function (also called the LPS array, for “longest proper prefix which is also a suffix”) records, for every position in needle, the length of its longest proper prefix that is also a suffix ending there. A proper prefix is shorter than the whole string.

While building this array, if the next characters do not match, we fall back to the LPS value of the already matched prefix. That value is the longest shorter prefix that could still match, so previously checked characters do not need to be revisited. The same invariant drives the search: j is the length of the needle prefix matching the suffix ending just before i; after a mismatch, j = lps[j - 1] retains the longest viable overlapping prefix instead of restarting from the beginning.

An empty needle matches at index 0. Otherwise, the scan returns immediately when all of needle has matched; if the scan ends first, there is no match. The prefix array uses $O(M)$ space, and both its construction and the scan take linear time, for $O(N + M)$ total time, where $N$ and $M$ are the lengths of haystack and needle.

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;

        int[] lps = new int[m];
        for (int i = 1, prefixLength = 0; i < m; ) {
            if (needle.charAt(i) == needle.charAt(prefixLength)) {
                lps[i++] = ++prefixLength;
            } else if (prefixLength > 0) {
                prefixLength = lps[prefixLength - 1];
            } else {
                lps[i++] = 0;
            }
        }

        // Invariant: j is the longest needle prefix matching a suffix before i.
        for (int i = 0, j = 0; i < n; ) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == m) return i - m;
            } else if (j > 0) {
                // Keep the longest overlapping prefix that can still match.
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return -1;
    }
}