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^5
  • 1 <= a.length, b.length <= 5 * 10^5
  • s、a 和 b 只包含小写英文字母

**提示：**使用 KMP 或字符串哈希。

解题思路

这道题需要高效地找到字符串匹配和范围查找的结合。解题思路如下：

核心思想：

  1. 首先找到所有字符串 a 在 s 中的出现位置（记为 pos_a）
  2. 然后找到所有字符串 b 在 s 中的出现位置（记为 pos_b）
  3. 对于每个 pos_a 中的位置 i，检查是否存在 pos_b 中的位置 j 使得 |j - i| <= k

优化策略：

  • 字符串匹配：使用 KMP 算法或内置的字符串查找函数来高效匹配
  • 范围查找：对于每个 a 的位置 i，需要在 pos_b 中查找范围 [i-k, i+k] 内是否有元素。可以使用二分搜索优化

算法流程：

  1. 使用 KMP 或滑动窗口找到所有 a 和 b 的匹配位置
  2. 对 pos_b 排序（为了使用二分搜索）
  3. 遍历每个 a 的位置，使用二分搜索检查范围 [i-k, i+k] 内是否有 b 的位置
  4. 满足条件的 i 加入结果数组

时间复杂度主要由字符串匹配和二分搜索决定，相比暴力 O(n²) 解法有显著提升。

代码实现

class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        int n = s.length();
        vector<int> pos_a, pos_b;
        
        // 找到所有a的匹配位置
        for (int i = 0; i <= (int)n - (int)a.length(); i++) {
            if (s.substr(i, a.length()) == a) {
                pos_a.push_back(i);
            }
        }
        
        // 找到所有b的匹配位置
        for (int i = 0; i <= (int)n - (int)b.length(); i++) {
            if (s.substr(i, b.length()) == b) {
                pos_b.push_back(i);
            }
        }
        
        vector<int> result;
        
        // 对于每个a的位置，检查是否存在满足条件的b位置
        for (int i : pos_a) {
            // 使用二分搜索找到范围[i-k, i+k]内的b位置
            int left = i - k, right = i + k;
            auto it = lower_bound(pos_b.begin(), pos_b.end(), left);
            if (it != pos_b.end() && *it <= right) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        import bisect
        
        n = len(s)
        pos_a = []
        pos_b = []
        
        # 找到所有a的匹配位置
        for i in range(n - len(a) + 1):
            if s[i:i + len(a)] == a:
                pos_a.append(i)
        
        # 找到所有b的匹配位置
        for i in range(n - len(b) + 1):
            if s[i:i + len(b)] == b:
                pos_b.append(i)
        
        result = []
        
        # 对于每个a的位置，检查是否存在满足条件的b位置
        for i in pos_a:
            # 使用二分搜索找到范围[i-k, i+k]内的b位置
            left, right = i - k, i + k
            idx = bisect.bisect_left(pos_b, left)
            if idx < len(pos_b) and pos_b[idx] <= right:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> BeautifulIndices(string s, string a, string b, int k) {
        int n = s.Length;
        List<int> posA = new List<int>();
        List<int> posB = new List<int>();
        
        // 找到所有a的匹配位置
        for (int i = 0; i <= n - a.Length; i++) {
            if (s.Substring(i, a.Length) == a) {
                posA.Add(i);
            }
        }
        
        // 找到所有b的匹配位置
        for (int i = 0; i <= n - b.Length; i++) {
            if (s.Substring(i, b.Length) == b) {
                posB.Add(i);
            }
        }
        
        List<int> result = new List<int>();
        
        // 对于每个a的位置，检查是否存在满足条件的b位置
        foreach (int i in posA) {
            // 使用二分搜索找到范围[i-k, i+k]内的b位置
            int left = i - k, right = i + k;
            int idx = posB.BinarySearch(left);
            if (idx < 0) idx = ~idx;
            if (idx < posB.Count && posB[idx] <= right) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var beautifulIndices = function(s, a, b, k) {
    function kmpSearch(text, pattern) {
        const n = text.length;
        const m = pattern.length;
        if (m === 0) return [];
        
        // Build LPS array
        const lps = new Array(m).fill(0);
        let len = 0;
        let i = 1;
        
        while (i < m) {
            if (pattern[i] === pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len !== 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        // Search for pattern in text
        const result = [];
        i = 0;
        let j = 0;
        
        while (i < n) {
            if (pattern[j] === text[i]) {
                i++;
                j++;
            }
            
            if (j === m) {
                result.push(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] !== text[i]) {
                if (j !== 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return result;
    }
    
    const aIndices = kmpSearch(s, a);
    const bIndices = kmpSearch(s, b);
    
    const result = [];
    
    for (const i of aIndices) {
        let found = false;
        for (const j of bIndices) {
            if (Math.abs(i - j) <= k) {
                found = true;
                break;
            }
        }
        if (found) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n×(m+l) + A×log(B))，其中 n 是字符串 s 的长度，m 和 l 分别是字符串 a 和 b 的长度，A 是 a 的匹配次数，B 是 b 的匹配次数
空间复杂度O(A + B)，用于存储匹配位置