这道题的关键在于高效匹配子串并判断距离条件。由于数据规模可达 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 数组回退 j
        while (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 的 i
    int* result = (int*)malloc(posASize * sizeof(int));
    *returnSize = 0;
    
    // 维持一个指针 j 指向 posB，确保 j 尽可能靠近当前 i
    int 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 顺序产生，若需严格排序可调用 qsort（posA 本身是无序的？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, curA+k] 内时，j 不会右移超过它。

---

测试验证

以题目示例 s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 为例：

· posA 包含 [16, 33]（'my' 出现位置）
· posB 包含 [4, 18]（'squirrel' 出现位置）
· 对于 16：j 会停在 4（因为 4 + 15 >= 16），|16-4|=12 <=15 通过
· 对于 33：j 继续前移到 18，|33-18|=15 <=15 通过
· 最终返回 [16, 33]

该实现完全满足题目对效率和正确性的要求。

---

进一步优化：如果担心整数溢出或希望避免动态分配临时数组（posA 和 posB），也可以采用流式处理匹配一个就判断一个。但实现复杂度会显著增加，且 posB 仍需存储以供双指针使用。当前方案是清晰且高效的。