这道题的关键在于高效匹配子串并判断距离条件。由于数据规模可达 5 * 10^5使用 KMP 算法将匹配复杂度控制在 O(n)再用双指针快速筛选满足 |j - i| ≤ k 的结果。以下是完整的 C 语言实现已在核心逻辑处添加注释c#include stdio.h#include stdlib.h#include string.h// 计算模式串的 next 数组前缀函数void buildNext(const char* pattern, int m, int* next) {next[0] 0;int j 0; // j 表示当前已匹配的前缀长度for (int i 1; i m; i) {// 失配时回退利用已计算的前缀信息while (j 0 pattern[i] ! pattern[j]) {j next[j - 1];}if (pattern[i] pattern[j]) {j;}next[i] j;}}// KMP 搜索返回文本串中所有模式串出现的起始下标int* kmpSearch(const char* text, const char* pattern, int* returnSize) {int n strlen(text);int m strlen(pattern);// 分配 next 数组int* next (int*)malloc(m * sizeof(int));buildNext(pattern, m, next);// 动态存储匹配位置最多 n 个int* positions (int*)malloc(n * sizeof(int));*returnSize 0;int j 0; // 模式串当前匹配位置for (int i 0; i n; i) {// 失配时根据 next 数组回退 jwhile (j 0 text[i] ! pattern[j]) {j next[j - 1];}if (text[i] pattern[j]) {j;}// 完全匹配成功if (j m) {positions[(*returnSize)] i - m 1;j next[j - 1]; // 继续寻找重叠匹配}}free(next);return positions;}// 比较函数用于 qsort升序int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b;}/*** 核心函数找出所有美丽下标* s: 主字符串* a: 模式串 a* b: 模式串 b* k: 距离阈值* returnSize: 返回结果数组的大小*/int* beautifulIndices(char* s, char* a, char* b, int k, int* returnSize) {// 1. 用 KMP 找出 a 和 b 的所有匹配起始下标int posASize 0, posBSize 0;int* posA kmpSearch(s, a, posASize);int* posB kmpSearch(s, b, posBSize);// 2. 如果 a 没有匹配直接返回空if (posASize 0) {*returnSize 0;free(posA);free(posB);return NULL;}// 3. 双指针筛选满足 |j - i| k 的 iint* result (int*)malloc(posASize * sizeof(int));*returnSize 0;// 维持一个指针 j 指向 posB确保 j 尽可能靠近当前 iint j 0;for (int i 0; i posASize; i) {int curA posA[i];// 将 j 移动到 posB[j] 在区间 [curA - k, curA k] 附近// 如果 posB[j] k curA说明当前 b 的位置太靠左需要右移while (j posBSize posB[j] k curA) {j;}// 检查当前 posB[j] 是否在合法距离内if (j posBSize abs(curA - posB[j]) k) {result[(*returnSize)] curA;}}// 4. 释放内存free(posA);free(posB);// 5. 结果已按原 posA 顺序产生若需严格排序可调用 qsortposA 本身是无序的KMP 返回有序这里保险if (*returnSize 0) {qsort(result, *returnSize, sizeof(int), cmp);}return result;}---算法思路与复杂度分析1. 高效匹配子串KMP使用 KMP 算法分别找出 a 和 b 在 s 中的所有起始下标。相比暴力匹配KMP 利用前缀函数next 数组避免重复比较时间复杂度 O(|s| |a|) 和 O(|s| |b|)。2. 双指针筛选美丽下标得到 posA 和 posB 两个有序数组后对于每个 posA[i]我们移动指针 j 指向 posB 中第一个满足 posB[j] k posA[i] 的位置。此时若 |posA[i] - posB[j]| k则 posA[i] 为美丽下标。由于 posA 和 posB 均递增j 指针无需回退整体线性扫描 O(|posA| |posB|)。3. 空间与时间复杂度· 时间复杂度O(|s| |a| |b| |posA| |posB|)即线性。· 空间复杂度存储 posA 和 posB 的数组最坏 O(|s|)。---关键细节说明· next 数组的含义next[i] 表示模式串前缀 pattern[0..i] 中最长相等真前后缀的长度。失配时利用它快速回退避免从头匹配。· KMP 搜索后的回退匹配成功后令 j next[j-1]以便继续寻找重叠出现的子串。· 双指针条件只需检查 posB[j] 而不需检查 posB[j-1]因为若 posB[j-1] 符合条件一定会被更早的 i 触发 j 左移逻辑且由指针移动规则可知当 posB[j-1] 在 [curA-k, curAk] 内时j 不会右移超过它。---测试验证以题目示例 s isawsquirrelnearmysquirrelhouseohmy, a my, b squirrel, k 15 为例· posA 包含 [16, 33]my 出现位置· posB 包含 [4, 18]squirrel 出现位置· 对于 16j 会停在 4因为 4 15 16|16-4|12 15 通过· 对于 33j 继续前移到 18|33-18|15 15 通过· 最终返回 [16, 33]该实现完全满足题目对效率和正确性的要求。---进一步优化如果担心整数溢出或希望避免动态分配临时数组posA 和 posB也可以采用流式处理匹配一个就判断一个。但实现复杂度会显著增加且 posB 仍需存储以供双指针使用。当前方案是清晰且高效的。