题目描述

给你两个字符串 s 和 pattern。

如果一个字符串 x 修改 至多 一个字符会变成 y，那么我们称它与 y 几乎相等。

请你返回 s 中下标 最小 的 子字符串，它与 pattern 几乎相等。如果不存在，返回 -1。

子字符串 是字符串中的一个 非空 连续的字符序列。

样例

入：s = "abcdefg", pattern = "bcdffg"

输出：1

解释：

将子字符串 s[1..6] == "bcdefg" 中 s[4] 变为 "f"，得到 "bcdffg"。

输入：s = "ababbababa", pattern = "bacaba"

输出：4

解释：

将子字符串 s[4..9] == "bababa" 中 s[6] 变为 "c"，得到 "bacaba"。

输入：s = "abcd", pattern = "dba"

输出：-1

输入：s = "dde", pattern = "d"

输出：0

限制

• 1 <= pattern.length < s.length <= 3 * 10^5
• s 和 pattern 都只包含小写英文字母。

进阶：如果题目变为 至多 k 个 连续 字符可以被修改，你可以想出解法吗？

算法

(二分，字符串哈希) $O(n \log m)$

1. 对于位置 $s(i)$，二分找到最大的长度 $j$，满足 $s(i, \dots, i + j - 1)$ 与 $pattern$ 的前 $j$ 个字符是相同的。二分的判定可以通过字符串哈希进行。
2. 如果最大的长度为 $m$，或者 $s$ 以 $i + j + 1$ 开头的字符串与 $pattern$ 的后缀相同，则视为找到了几乎相同的子串，输出答案。
3. 对于进阶问题，将判断条件修改为以 $i + j + k$ 开头的字符串即可。

时间复杂度

• 预处理哈希的时间复杂度为 $O(n)$。
• 每个位置二分的区间长度为 $m$。
• 故总时间复杂度为 $O(n \log m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储字符串哈希的结果。

C++ 代码

#define ULL unsigned long long

const int M1 = 131, M2 = 13331;
const int N = 300010;

ULL power1[N], power2[N];

auto init = []{
    power1[0] = power2[0] = 1;
    for (int i = 1; i < N; i++) {
        power1[i] = power1[i - 1] * M1;
        power2[i] = power2[i - 1] * M2;
    }

    return 0;
}();

class Solution {
private:
    vector<ULL> s1, s2, p1, p2;

    bool eq(int s, int p, int len) {
        ULL hs, hp;
        hs = s1[s + len - 1] - s1[s - 1] * power1[len];
        hp = p1[p + len - 1] - p1[p - 1] * power1[len];

        if (hs != hp)
            return false;

        hs = s2[s + len - 1] - s2[s - 1] * power2[len];
        hp = p2[p + len - 1] - p2[p - 1] * power2[len];

        return hs == hp;
    }

public:
    int minStartingIndex(string s, string pattern) {
        const int n = s.size(), m = pattern.size();

        s1.resize(n + 1); s2.resize(n + 1);
        s1[0] = s2[0] = 1;
        for (int i = 1; i <= n; i++) {
            s1[i] = s1[i - 1] * M1 + s[i - 1] - 'a' + 1;
            s2[i] = s2[i - 1] * M2 + s[i - 1] - 'a' + 1;
        }

        p1.resize(m + 1); p2.resize(m + 1);
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= m; i++) {
            p1[i] = p1[i - 1] * M1 + pattern[i - 1] - 'a' + 1;
            p2[i] = p2[i - 1] * M2 + pattern[i - 1] - 'a' + 1;
        }

        for (int i = 1; i <= n - m + 1; i++) {
            int l = 0, r = m;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (eq(i, 1, mid + 1)) l = mid + 1;
                else r = mid;
            }

            if (l == m)
                return i - 1;

            if (eq(i + l + 1, l + 2, m - l - 1))
                return i - 1;
        }

        return -1;
    }
};