以下是 LeetCode 3303 的 C 语言实现使用 Z-FunctionZ 数组 算法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 sint 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));// 反转 patternfor (int i 0; i m; i) {str2[i] pattern[m - 1 - i];}// 反转 sfor (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;// 枚举每个可能的起始位置 ifor (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 后拼接避免多次调用 strrevz1[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/其他语言完全一致。
Kimi LeetCode 3303. 第一个几乎相等子字符串的下标 C语言实现
以下是 LeetCode 3303 的 C 语言实现使用 Z-FunctionZ 数组 算法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 sint 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));// 反转 patternfor (int i 0; i m; i) {str2[i] pattern[m - 1 - i];}// 反转 sfor (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;// 枚举每个可能的起始位置 ifor (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 后拼接避免多次调用 strrevz1[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/其他语言完全一致。
