Implementing strStr() with the KMP Algorithm

Given a haystack string and a needle string, locate the index of the first occurrence of the needle. The Knuth–Morris–Pratt (KMP) algorithm avoids redundant comparisons by precomputing a prefix table (often called the LPS – Longest Proper Prefix which is also Suffix – array).

First, construct the LPS array for the pattern:

vector<int> computeLPS(const string& pattern) {
    int n = pattern.size();
    vector<int> lps(n, 0);
    int length = 0;
    for (int i = 1; i < n; ++i) {
        while (length > 0 && pattern[i] != pattern[length]) {
            length = lps[length - 1];
        }
        if (pattern[i] == pattern[length]) {
            ++length;
        }
        lps[i] = length;
    }
    return lps;
}

Then use the LPS array to skip unnecessary checks while scanning the haystack:

int strStr(const string& haystack, const string& needle) {
    if (needle.empty()) return 0;
    vector<int> lps = computeLPS(needle);
    int j = 0; // index in needle
    for (int i = 0; i < haystack.size(); ++i) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = lps[j - 1];
        }
        if (haystack[i] == needle[j]) {
            ++j;
        }
        if (j == needle.size()) {
            return i - j + 1;
        }
    }
    return -1;
}

When a mismatch occurs, the pattern pointer j falls back to lps[j-1], ensuring that previously matched characters are not re-examined from scratch.

Detecting a Repeated Substring Pattern

For LeetCode 459, repeatedSubstringPattern determines whether a string can be formed by repeating a single substring multiple times. This can be solved efficiently using the same LPS array. Let n = s.length() and len = lps[n-1]. If len > 0 and n % (n - len) == 0, theidea is that the string is composed of repetitions of its prefix of length n - len.

bool repeatedSubstringPattern(const string& s) {
    int n = s.size();
    vector<int> lps = computeLPS(s);
    int lastLps = lps.back();
    return lastLps > 0 && n % (n - lastLps) == 0;
}

The function reuses the computeLPS helper defined above. This approach works in linear time and avoids generating substrings explicitly.

Two Pointers in String Manipulation

Many string problems banefit from the two‑pointer technique. For in‑place reversal, removing extra spaces, or partitioning a string, a pair of indices (often named left and right) can traverse the characters without allocating additional memory. The KMP algorithm itself can be viewed as a two‑pointer method where one pointer scans the text and the other tracks the pattern, moving intelligent via the LPS table. This perspective unifies several classic patterns such as array element removal, string reversal, and efficient substring search.