C语言求字符串最大对称子串长度的3种解法
在C语言开发中，寻找字符串中的最大对称子串（即最长回文子串）是经典的算法问题。常见的解决方案包括时间复杂度为O(n³)的全遍历暴力匹配、O(n²)的原串翻转错位比较法，以及通过状态递推实现的O(n)线性时间复杂度算法。本文将逐一解析这三种方法的原理，并提供高效的C语言实现代码。
什么是最大对称子串
最大对称子串是指在一个给定的字符串中，正读和反读都相同的连续子串，且其长度在所有可能的对称子串中最长。例如，在字符串“avvbeeb”中，最长的对称子串是“beeb”，长度为4。
方法一：全遍历暴力匹配 O(n³)
这是最直观的解题思路。核心思想是枚举字符串中所有可能的子串，并逐个判断它们是否对称。
第1步：生成所有子串
使用两层循环（或指针i和
第2步：判断对称性
对每个生成的子串，检查其是否为回文串。如果是对称的，则记录其长度，并与当前已知的最大长度进行比较更新。
缺点：由于需要遍历所有子串并逐一验证，时间复杂度高达O(n³)，仅在数据量极小可用，实际应用价值有限。
方法二：原串翻转错位比较 O(n²)
此方法利用了回文的特性：如果一个子串是对称的，那么它在原串和翻转串中必然以某种对齐方式出现。
第1步：构建翻转串
假设原串为 str1，将其内容完全反转得到 str2。例如 str1 = "avvbeeb"，则 str2 = "beebvva"。
第2步：错位比对
将 str1 保持不动，让 str2 从右向左依次偏移对齐，比较上下对应的字符序列：
- 初始对齐：比较首尾，看是否有共同的前缀/后缀。
- 逐步偏移：每次将
str2向左移动一位，比较新对齐位置的字符序列。
当某一位置的字符序列完全匹配时，该序列即为一个公共的子串。虽然这不能保证一定是回文，但结合回文定义，最长匹配的公共子串往往对应最长回文子串的一部分。这种方法通过两次主要遍历和错位比较，将复杂度降低至O(n²)。
方法三：动态规划递推优化 O(n)
这是最高效的方法。通过观察回文子串的性质，我们可以推导出当前位置的最长回文长度与前一位状态的关系，从而实现一次遍历求解。
逻辑推导
设 f(n) 表示以第 n 位字符结尾的最长对称子串长度。当我们考虑第 n+1 位字符 A[n+1] 时：
- 向外扩展情况：如果
A[n+1]与其左侧距离f(n)位置的字符A[n-f(n)-1]相同，说明当前的对称区间可以向两侧各扩展一个字符。此时，新的长度为f(n+1) = f(n) + 2。这要求A[n-f(n)-1] == A[n+1]且边界有效。 - 连续相同字符处理：如果上述条件不满足，或者
A[n+1]与相邻字符重复（如 "aaaa"），我们需要单独计算以A[n+1]结尾的连续相同字符段的长度，并取最大值。
算法步骤
- 初始化：创建数组
record，record[i]存储以索引i结尾的最长对称子串长度。初始时maxlen = 1。 - 状态转移：遍历字符串，对于每个位置
i：
a. 先尝试利用前一位的状态进行扩展：如果i - record[i-1] - 1 >= 0且inp[i] == inp[i - record[i-1] - 1]，则候选长度为record[i-1] + 2。
b. 再处理连续相同字符：若inp[i] == inp[i-k]，增加连续长度k。
c. 取两者较大值作为record[i]。 - 更新全局最大：每计算完一个位置，更新全局最大长度
maxlen。
C语言实现
以下是基于上述逻辑的完整 C 语言代码实现。代码中包含了详细的状态记录和长度比较逻辑。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// 求最大对称子串长度
int FUN(char *inp) {
int maxlen = 1; // 最大长度，至少为1
int len = strlen(inp);
// record数组用于存放以每一位结尾的最长对称子串长度
int record[len];
record[0] = 1;
int i = 1;
for (; i < len; i++) {
int max = 1;
// 情况1：尝试利用前一位的状态向外扩展
// 检查左边界是否存在，且左外侧字符与当前字符相同
if ((i - record[i-1] - 1) >= 0 && inp[i] == inp[i - record[i-1] - 1]) {
max = (record[i-1] + 2) > max ? (record[i-1] + 2) : max;
}
// 情况2：处理连续相同字符的情况
// 例如本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
