找出数组中的美丽下标 II

难度: Hard

给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。

如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：

0 <= i <= s.length - a.length
s[i..(i + a.length - 1)] == a
存在下标 j 使得：
- 0 <= j <= s.length - b.length
- s[j..(j + b.length - 1)] == b
- |j - i| <= k

以数组形式按 从小到大排序 返回美丽下标。

示例 1：

输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
输出：[16,33]
解释：存在 2 个美丽下标：[16,33]。
- 下标 16 是美丽下标，因为 s[16..17] == "my" ，且存在下标 4 ，满足 s[4..11] == "squirrel" 且 |16 - 4| <= 15 。
- 下标 33 是美丽下标，因为 s[33..34] == "my" ，且存在下标 18 ，满足 s[18..25] == "squirrel" 且 |33 - 18| <= 15 。
因此返回 [16,33] 作为结果。

示例 2：

输入：s = "abcd", a = "a", b = "a", k = 4
输出：[0]
解释：存在 1 个美丽下标：[0]。
- 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。
因此返回 [0] 作为结果。

提示：

1 <= k <= s.length <= 5 * 10⁵
1 <= a.length, b.length <= 5 * 10⁵
s、a、和 b 只包含小写英文字母。

Submission

运行时间: 344 ms

内存: 52.3 MB

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        def g(a, i):
            i = a.find(a[:i], i)
            if i < 0:
                return len(a)
            k, v = divmod(len(a), i)
            if a[-v:] == a[:v] and a.startswith(a[:i] * k):
                return i
            return g(a, i + 1)

        def f0(a):
            t = len(s) - len(a)
            i, q = 0, []
            while i <= t:
                i = s.find(a, i)
                if i < 0:
                    break
                q.append(i)
                i += 1
            return q
            
        def f(a):
            q, n = set(a), len(a)
            i = g(a, max(map(a.find, q)) + 1) if len(q) > 1 else 1
            if i >= n:
                return f0(a)
            j, n = ceil(n / i) - 1, n % i
            q, ans = f(a[:i]), []
            for k, q in groupby(pairwise(q), key=lambda x: x[1] - x[0]):
                if k != i:
                    continue
                q = list(chain(next(q), (x[1] for x in q)))
                if len(q) > j:
                    ans.extend(q[:-j])
                    if n:
                        k = q[-j]
                        if a.startswith(a[k:k + n]):
                            ans.append(k)
            return ans
            
        if a == b:
            return f(a)
        a, b, q = f(a), f(b), []
        while a:
            i = a.pop()
            j = i + k
            while b and b[-1] > j:
                b.pop()
            if b and b[-1] >= i - k:
                q.append(i)
        return q[::-1]

Explain

本题解的主要思路是找出所有满足特定条件的下标对。首先，使用辅助函数g来找到字符串a或b中最小的重复模式长度，这有助于后续的优化。函数f0是用来找出字符串s中所有包含字符串a或b的起始下标。函数f用于优化搜索过程，如果字符串a或b有重复的模式，f会尽量减少搜索次数，从而只搜索可能的开始下标。最后，根据这些起始下标，检查它们之间的距离是否满足条件k。如果a和b是同一个字符串，可以进一步减少计算量。最终，将满足条件的下标存入结果数组并返回。

时间复杂度: O(n * m)

空间复杂度: O(n)

# Solution class to solve the problem

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        # Helper function to detect smallest repeating pattern
        def g(a, i):
            i = a.find(a[:i], i)
            if i < 0:
                return len(a)
            k, v = divmod(len(a), i)
            if a[-v:] == a[:v] and a.startswith(a[:i] * k):
                return i
            return g(a, i + 1)

        # Find all occurrences of string a in s
        def f0(a):
            t = len(s) - len(a)
            i, q = 0, []
            while i <= t:
                i = s.find(a, i)
                if i < 0:
                    break
                q.append(i)
                i += 1
            return q
            
        # Optimized search for start indices
        def f(a):
            q, n = set(a), len(a)
            i = g(a, max(map(a.find, q)) + 1) if len(q) > 1 else 1
            if i >= n:
                return f0(a)
            j, n = ceil(n / i) - 1, n % i
            q, ans = f(a[:i]), []
            for k, q in groupby(pairwise(q), key=lambda x: x[1] - x[0]):
                if k != i:
                    continue
                q = list(chain(next(q), (x[1] for x in q)))
                if len(q) > j:
                    ans.extend(q[:-j])
                    if n:
                        k = q[-j]
                        if a.startswith(a[k:k + n]):
                            ans.append(k)
            return ans
            
        # Check and combine indices from a and b according to the distance k
        if a == b:
            return f(a)
        a, b, q = f(a), f(b), []
        while a:
            i = a.pop()
            j = i + k
            while b and b[-1] > j:
                b.pop()
            if b and b[-1] >= i - k:
                q.append(i)
        return q[::-1]

Explore

函数`g`通过递归查找字符串中的最小重复模式长度。它首先尝试在字符串`a`中找到从某个位置`i`开始的子字符串`a[:i]`的下一个出现，如果找到了，会检查这个位置是否能够让整个字符串被这个长度整除且模式正确。如果不符合，`g`会递归地尝试下一个长度。虽然这种递归逻辑可能看起来会检查某些长度多次，但实际上每次递归调用时考虑的起始位置`i`都在增加，这意味着它不会重复检查相同的长度，而是逐步增加探索的长度，确保了寻找最小重复模式的高效性。

函数`f0`在找到字符串`a`在字符串`s`中的一个匹配后，索引`i`加1再继续搜索是为了找出所有可能的匹配位置，包括那些重叠的匹配。如果我们不将`i`增加，那么搜索就会在找到的第一个匹配处停止，无法继续向后查找。虽然这样做确实能找到所有匹配，包括重叠的，但它也增加了搜索的时间复杂度，因为每次找到匹配后只前进一个字符，会进行大量的重复检查。在某些情况下，可以考虑优化这个过程，比如在找到匹配后跳过整个匹配长度，但这需要根据具体情况调整策略。

函数`f`通过检测字符串中的重复模式来决定是否使用优化搜索。当字符串较短时，这种优化可能不会带来显著的性能提升，因为重复模式可能不存在或者模式长度接近整个字符串长度，这使得优化的效果不明显。在这种情况下，简单的全搜索（即逐一检查每个可能的位置）可能更为直接和高效。然而，如果字符串较长且存在明显的重复模式，优化搜索可以显著减少搜索次数，通过跳过一些不可能的匹配位置来提高效率。因此，是否使用优化搜索应根据字符串的实际情况和特性来决定，特别是在字符串很短的情况下可能不需要复杂的优化。