美文网首页
C语言实现求最长回文子串

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

作者: JerryShieh | 来源:发表于2020-08-04 18:14 被阅读0次

最长回文子串的概念

回文串是指正序和反序都一样的字符串,例如:
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;
}

相关文章

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

    最长回文子串的概念 回文串是指正序和反序都一样的字符串,例如:Str1 = "AbbA",则Str1的最长回文子串...

  • Manacher's Algorithm算法分析Java

    Manacher's Algorithm俗称马拉车算法,对于求字符串中最长回文子串效率极高。 在求最长回文子串的时...

  • LeetCode 第647题:回文子串

    1、前言 2、思路 此题与最长回文子串很像,只不过那个是求最长的回文子串,而这个是求回文子串的数目。但是他们的解法...

  • 最长回文子串

    最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串,求它的最长回文子串长度...

  • LeetCode 5. 最长回文子串(Longest Palin

    5. 最长回文子串 切题 一、Clarification 求最长回文子串,这里有几个特殊情况需要考虑1、空字符串,...

  • 最长回文子串问题—Manacher算法

    最长回文串问题是一个经典的算法题。 0. 问题定义 最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果...

  • 字符串---Manacher

    求最长回文子串 求一个串中的回文子串,首先将字符串处理成奇数个。如"abbc"处理成Ma = "$ a # b #...

  • 最长回文子串

    问题定义 最长回文子串问题:给定一个字符串,求它的最长回文子串长度。 解法1:暴力解法 找到字符串的所有子串,判断...

  • 字符串

    最长回文子串 1. 题目 已知一个只包含大小写的字符串,求用该字符串可以生成的最长回文子串的长度。 2. 思路 首...

  • 字符串最长回文子串

    字符串最长回文子串 题目描述: 给定一个字符串,求它的最长回文子串的长度。 分析和解法: 最容易想到的办法是枚举所...

网友评论

      本文标题:C语言实现求最长回文子串

      本文链接:https://www.haomeiwen.com/subject/qjnwrktx.html