find-the-occurrence-of-first-almost-equal-substring.cpp

// Time:  O(n + m)
// Space: O(n + m)

// z-function
class Solution {
public:
    int minStartingIndex(string s, string pattern) {
        static const int K = 1;

        // Template: https://cp-algorithms.com/string/z-function.html
        const auto& z_function = [](const string& s) {  // Time: O(n), Space: O(n)
            vector<int> z(size(s));
            for (int i = 1, l = 0, r = 0; i < size(z); ++i) {
                if (i <= r) {
                    z[i] = min(r - i + 1, z[i - l]);
                }
                while (i + z[i] < size(z) && s[z[i]] == s[i + z[i]]) {
                    ++z[i];
                }
                if (i + z[i] - 1 > r) {
                    l = i, r = i + z[i] - 1;
                }
            }
            return z;
        };

        const auto& z1 = z_function(pattern + s);
        reverse(begin(pattern), end(pattern));
        reverse(begin(s), end(s));
        const auto& z2 = z_function(pattern + s);
        for (int i = 0; i < size(s) - size(pattern) + 1; ++i) {
            if (z1[size(pattern) + i] + K + z2[size(s) - i] >= size(pattern)) {
                return i;
            }
        }
        return -1;
    }
};