C语言实现求最长回文子串

最长回文子串的概念

回文串是指正序和反序都一样的字符串，例如：
Str1 = "AbbA"，则Str1的最长回文子串是它本身“AbbA”，最长回文长度为4；
Str2="AABBAb"，则Str2的最长回文子串是“ABBA”，最长回文长度为4。

解决方案

• 暴力破解
  列出所有子串，判断子串是否为回文串。

• 利用最长公共子串求解
  根据回文串的概念，可将原串反序得到新串，然后对原串与新串求最长公共子串即可。最长公共子串的算法可参考https://www.jianshu.com/p/64dfcef92d5f

• 利用Manacher算法
  利用回文串的对称特性，可将算法的时间复杂度降为O(n)，代码如下：

int initManacher(const char* rawStr, char* const newStr)
{
    int len = strlen(rawStr);
    newStr[0] = '$';
    newStr[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        newStr[j++] = rawStr[i];
        newStr[j++] = '#';
    }

    newStr[j] = '\0';
    return j;
}

int manacher(const char* rawStr)
{
    char* newStr = (char*)calloc(strlen(rawStr) * 2 + 3, sizeof(char));
    int* p = (int*)calloc(strlen(rawStr) * 2 + 3, sizeof(int)); // p[i]的值表示以i为中心的最长回文半径
    int len = initManacher(rawStr, newStr);  // 将字符串的长度转为奇数并以"$"开始，"\0"结尾
    int max_len = -1;  // 最长回文长度

    int center = 0;     // center的主要作用是作为回文的中心，这个轴中心是从左往右跳跃着变化的
    int radius = 0;     // 以center为中心的最大回文半径的下标，radius - center为以center为中心的最大回文半径，也即radius - center == p[center]

    for (int i = 1; i < len; i++)
    {
        if (i < radius)     // 如果i在以center为中心，回文半径为radius - center的范围内，则可以利用回文的特性，快速求取p[i]的值。 p[2 * center - i]是i以center为中心的对称点的值
            p[i] = min(p[2 * center - i], radius - i);  // 计算出p[i]的最小可能值
        else                // 如果不在该半径内，则无法利用回文的特性，只能按普通的方法来一步一步求取p[i]的准确值，最开始的默认值为1
            p[i] = 1;

        // 因为上面计算所得的p[i]值为最小可能值，p[i]的准确值还需通过不断扩展来判断，这个while循环不断扩展以i为中心的回文半径（i当前的回文半径外的第一个位置的值如果两边都相等，说明回文半径还可以加1）。注意，这里不需边界判断，因为左有'$',右有'\0'
        while (newStr[i - p[i]] == newStr[i + p[i]])
            p[i]++;

        // 我们每走一步 i，都要和 radius 比较，我们希望 radius 尽可能的远，这样才能更有机会执行 if (i < radius)这句代码，从而提高效率
        if (radius < i + p[i])
        {
            center = i;     // 更新center的位置
            radius = i + p[i];  // 更新为以新center为中心的最大回文半径
        }

        max_len = max(max_len, p[i] - 1);
    }

    free(newStr);
    free(p);
    return max_len;
}