以下是 LeetCode 3303 的 C 语言实现，使用 Z-Function（Z 数组） 算法：
```c
#include <string.h>
// 计算 Z-Function 数组
// z[i] 表示 s[i..n) 与 s[0..n) 的最长公共前缀长度
static void zFunction(const char *s, int n, int *z) {
int l = 0, r = 0;
z[0] = 0;
for (int i = 1; i < n; i++) {
if (i < r) {
z[i] = (r – i < z[i – l]) ? r – i : z[i – l];
} else {
z[i] = 0;
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
}
int minStartingIndex(char *s, char *pattern) {
int n = strlen(s);
int m = strlen(pattern);
// 正向匹配：pattern + s
int len1 = m + n;
char *str1 = (char *)malloc((len1 + 1) * sizeof(char));
strcpy(str1, pattern);
strcpy(str1 + m, s);
int *z1 = (int *)malloc(len1 * sizeof(int));
zFunction(str1, len1, z1);
// 反向匹配：reverse(pattern) + reverse(s)
int len2 = m + n;
char *str2 = (char *)malloc((len2 + 1) * sizeof(char));
// 反转 pattern
for (int i = 0; i < m; i++) {
str2[i] = pattern[m – 1 – i];
}
// 反转 s
for (int i = 0; i < n; i++) {
str2[m + i] = s[n – 1 – i];
}
str2[len2] = '\\0';
int *z2 = (int *)malloc(len2 * sizeof(int));
zFunction(str2, len2, z2);
int result = -1;
// 枚举每个可能的起始位置 i
for (int i = 0; i <= n – m; i++) {
// z1[m + i]：从 s[i] 开始正向匹配 pattern 的最长前缀长度
// z2[n – i]：从 s[i] 末尾反向匹配 pattern 的最长后缀长度
// 两者之和 >= m – 1 说明中间最多只有 1 个字符不匹配
if (z1[m + i] + z2[n – i] >= m – 1) {
result = i;
break;
}
}
free(str1);
free(z1);
free(str2);
free(z2);
return result;
}
```
关键点
要点 说明
`malloc` + `free` C 中需手动管理内存，计算完 Z 数组后及时释放
字符串拼接 用 `strcpy` 将 `pattern` 和 `s` 拼接到新分配的缓冲区
反向构造 分别反转 `pattern` 和 `s` 后拼接，避免多次调用 `strrev`
`z1[m + i] + z2[n – i]` 正向前缀 + 反向后缀覆盖 `m-1` 个字符，即汉明距离 ≤ 1
复杂度
– 时间复杂度：O(n + m)，两次 Z-Function 均为线性遍历
– 空间复杂度：O(n + m)，两个拼接字符串和两个 Z 数组
与 Java 版本的区别
C 语言没有内置字符串反转和动态数组，需要手动：
1. `malloc` 分配拼接字符串的内存
2. 循环反转字符构造反向字符串
3. 手动 `free` 释放所有动态分配的内存
核心算法逻辑（Z-Function + 双数组匹配）与 Java/其他语言完全一致。
