精华内容
下载资源
问答
  • 最长回文串算法

    2016-01-29 14:16:05
    总的来说,最长回文串算法分为以下几种。暴力法通过遍历整个字符串来说实现对最长回文串的查找 首先一个字符串所有子串,个数为n2个,然后逐个判断遍历即可,算法复杂度O(n3)动态规划中心扩展法Manacher算法这是一...

    总的来说,最长回文串算法分为以下几种。

    暴力法

    通过遍历整个字符串来说实现对最长回文串的查找
    首先一个字符串所有子串,个数为n2个,然后逐个判断遍历即可,算法复杂度O(n3)
    代码如下:

    def is_palindrome(s):
        str_length = len(s)
    
        for i in range(str_length / 2):
            if s[i] != s[str_length - 1 - i]:
                return False
    
        return True
    
    # 暴力求解法
    def algorithm1(s):
        length = len(s)
    
        for i in range(length):
            for j in range(i + 1):
                if is_palindrome(s[j: length - i + j]):
                    return len(s[j: length - i + j])
    
        return 1

    动态规划

    中心扩展法

    该算法感觉是Manacher算法的前身吧,使用字符中心向两侧扩展,这样,只需要进行遍历字符串一次,然后针对每个字符进行单独的判断即可。
    代码如下:

    
    def change(s):
        l = []
        for c in s:
            l.append(c)
    
        return "@#%s#" % "#".join(l)
    
    # 中心求解法
    def algorithm3(s):
        s = change(s)
        flag = 0
        for i in range(2, len(s) - 2):
            temp = 1
            while s[i - temp] == s[i + temp]:
                temp += 1
    
            if temp > flag:
                flag = temp
    
        return flag - 1

    其实中心求解法完全可以不修改字符串,不过那样处理起来比较麻烦,代码写起来费力一些。

    Manacher算法

    这是一个比较牛掰的算法,其实感觉是对中心扩展法的优化,但是我搞了好久才大体搞明白,主要因为其中有几个难点

    • 需要对字符串进行变换
    • 针对辅助数组的使用优化计算比较难理解
    • 算法复杂度分析

    这个方法的牛掰之处就在于它的算法复杂度是O(n)的,想出暴力解法很简单,但是直观来看,算法复杂度差太多了。

    字符串变换

    因为Manacher有个核心定义,叫做P[i]
    p[i] : 以i为中心的的回文半径长度
    因为该数组,所以必须对字符串进行变换。因为当且仅当回文为奇数长度字符串,才可能存在P[i]这种定义

    辅助数组优化计算

    python实现的代码如下:

    def change(s):
        l = []
        for c in s:
            l.append(c)
    
        return "@#%s#" % "#".join(l)
    
    # Manacher算法
    def algorithm4(s):
        s = change(s)
        p = [0] * len(s)
        index = 0
        for i in range(2, len(s) - 2):
            if p[index] + index > i:
                p[i] = min(p[2 * index - i], p[index] + index - i)
            else:
                p[i] = 1
    
            while s[i - p[i]] == s[i + p[i]]:
                p[i] += 1
    
            if index + p[index] < i + p[i]:
                index = i
    
        return max(p) - 1

    其中有个判断,为 p[index] + index > i
    其代表的意思可以结合P数组的概念进行理解, p[index]为以index为中心的回文半径长度,index为其索引值,
    所以 p[index] + index的意思为以index为核心的回文辐射范围
    if p[index] + index > i:说明下一个遍历点,在以index为核心的回文辐射范围之内,既然在辐射范围之内,说明p的起始计算位置至少要从p[2 * index -i],或者p[index] + index - i开始。
    这里比较绕。
    这里解释一下

    • p[2 * index - i]:因为 2 * index - i 和 i 关于 index是对称的,而根据回文本身的特点,我们就知道 p[i] >= p[2 * index - i]
    • p[index] + index - i:这个值由其实由辐射范围去掉了i。

    两者的概念很类似,其实主要就是看对称点的,根据对称点p[2 * index - i],如果该值超过了p[index]的辐射范围,那么就取值p[index] + index -i,否则就取值本身。
    说起来比较绕,其实自己画个图发现这个还是比较容易理解的。

    算法复杂度分析

    这个算法在我看来,是比之前中心算法的一个优化,但是我一点都看不出来为什么该算法的复杂度为O(n),后来看了很多别人的讲解。
    manacher算法只需要线性扫描一遍预处理后的字符串。
    经过优化后,p是求解过程中,对字符串的每个字符,扫描最多只会2次,时间复杂度必然为O(n)

    展开全文
  • python最长回文串算法

    2020-09-20 10:32:51
    主要为大家详细介绍了python最长回文串算法的实践,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Manachar算法主要是处理字符串中关于回文串的问题的,它可以在 O(n) 的时间处理出以字符串中每一个字符为中心的回文串半径,由于将原字符串处理成两倍长度的新串,在每两个字符之间加入一个特定的特殊字符,因此...

     Manachar算法主要是处理字符串中关于回文串的问题的,它可以在 O(n) 的时间处理出以字符串中每一个字符为中心的回文串半径,由于将原字符串处理成两倍长度的新串,在每两个字符之间加入一个特定的特殊字符,因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。       ------摘自百度百科

    在介绍算法之前,首先介绍一下什么是回文串,所谓回文串,简单来说就是正着读和反着读都是一样的字符串,比如abba,noon等等,一个字符串的最长回文子串即为这个字符串的子串中,是回文串的最长的那个。

    计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串,并且判断这个子串是否为回文串,这个算法的时间复杂度为O(n^3)的,显然无法令人满意,稍微优化的一个算法是枚举回文串的中点,这里要分为两种情况,一种是回文串长度是奇数的情况,另一种是回文串长度是偶数的情况,枚举中点再判断是否是回文串,这样能把算法的时间复杂度降为O(n^2),但是当n比较大的时候仍然无法令人满意,Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串,达到了理论上的下界。

    一.通常解决的问题

    给定一个字符串,求出其最长回文子串。例如:
    (1)s="abcd", 最长回文长度为 1;
    (2)s="ababa", 最长回文长度为 5;
    (3)s="abccb", 最长回文长度为 4,即 bccb。

    经典例题:HDU3068


      以上问题的传统思路大概是,遍历每一个字符,以该字符为中点向两边查找。其时间复杂度为 O(n2),很不高效。而在 1975 年,一个叫 Manacher 的人发明了一个算法,Manacher 算法,也称马拉车算法,该算法可以把时间复杂度提升到 O(n)。下面来看看马拉车算法是如何工作的。

    二.算法原理

           奇偶变换:为处理字符串方便,现将给定的任意字符串进行处理,使所有可能的奇数/偶数长度的回文子串都转换成了奇数长度。具体就是在每个字符的两边都插入一个特殊的符号。比如hhjj变成 #h#h#j#j#, aba变成 #a#b#a#;为防止数组越界,可以在字符串的开始加入另一个特殊字符,比如“?#a#b#a#?” 。

    定义一个辅助数组int p[]p[i]表示以s_new[i]为中心的最长回文的半径,例如:

    i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
    s_new[i] $ # a # b # b # a # h # o # p # x # p #
    p[i]   1 2 1 4 5 2 1 2 1 2 1 2 1 2 1 6 1 2 1

    可以看出,p[i]-1正好是原字符串中最长回文串的长度。
      Manacher 算法之所以快,就快在对 p 数组的求法上有个捷径,看下图:

    设置两个变量,mx 和 id 。
      mx 代表以s_new[id]为中心的最长回文最右边界,也就是mx=id+p[id]
      假设我们现在求p[i],也就是以s_new[i]为中心的最长回文半径,如果i<mx,如上图,那么:

    if (i < mx)
    
    p[i] = min(p[2 * id - i], mx - i);

    2 * id -i其实就是等于 j ,p[j]表示以s_new[j]为中心的最长回文半径,见上图,因为 i 和 j 关于 id 对称,我们利用p[j]来加快查找。

    #include<stdio.h> 
    #include<iostream>  
    #include<cstring>
    #include<algorithm>  
    using namespace std;
    const int maxn=111111;
    char s[maxn];
    char s_new[maxn*2];
    int p[maxn*2];
    int Init(){
        int len = strlen(s);
        s_new[0] = '$';
        s_new[1] = '#';
        int j = 2;
        for (int i = 0; i < len; i++){
            s_new[j++] = s[i];
            s_new[j++] = '#';
        }
        s_new[j] = '\0';  
     	//printf("%s\n",s_new);
        return j;  //返回s_new的长度  
    }
    int Manacher(){
        int len = Init();  //取得新字符串长度并完成向s_new的转换  
        int maxLen = -1;   //最长回文长度  
        int id;
        int mx = 0;
        for (int i = 1; i < len; i++){
            if (i < mx)
                p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
            else
                p[i] = 1;
            while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断,因为左有'$',右有'\0'  
                p[i]++;
            //我们每走一步i,都要和mx比较,我们希望mx尽可能的远,这样才能更有机会执行if (i < mx)这句代码,从而提高效率 
            if (mx < i + p[i])  {
                id = i;
                mx = i + p[i];
            }
            maxLen = max(maxLen, p[i] - 1);
           // printf("%d %d %d\n",mx,id,maxLen);
        }
        /*for(int i=1;i<=len;i++)printf("%d ",p[i]);
        printf("\n");*/
        return maxLen;
    }
    int main(){
    	scanf("%s", s);
        printf("%d\n", Manacher());
    
     	return 0;
    }
    

     

    展开全文
  • 然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i]),比如S和P的对应关系: S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # P  1 2 1 2 5 2 1 ...

    题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=3068

    分析:

    本文分析摘自:http://www.felix021.com/blog/read.php?2040

      首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。

    下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";

    然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i]),比如S和P的对应关系:

    S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #

    P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1

    (p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)

    那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中id表示最大回文子串中心的位置,mx则为id+P[id],也就是最大回文子串的边界。

    然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。实际上如果把它写得复杂一点,理解起来会简单很多:

    //记j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点。
    if (mx - i > P[j])
        P[i] = P[j];
    else /* P[j] >= mx - i */
        P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。

    当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。



    当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。

    对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。

    于是代码如下:

    int FindMaxPalindrome(char* str)
    {
        int iMax = 0, i;
        int p[MAXN*2], index = 0, mx = 0;
        memset(p, 0, sizeof(p));
        for(i = 1; str[i] != '\0'; ++i)
        {
            p[i] = mx > i ? MIN(p[2*index-i], mx-i) : 1;
            while(str[i+p[i]] == str[i-p[i]])
                p[i]++;
            if(i+p[i] > mx)
            {
                mx = p[i] + i;
                index = i;
            }
            if(p[i] > iMax)
                iMax = p[i];
        }
        return iMax-1;
    }
    

    本题代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int MAXN = 110010;
    
    int MIN(int a, int b)
    {
        return a < b ? a : b;
    }
    
    void AddSpecialChar(char* str1, char* str2)
    {
        int i, j;
        int Len = strlen(str1);
        str2[0] = '$';
        str2[1] = '#';
        for(i = 0, j = 2; i < Len; ++i, j += 2)
            str2[j] = str1[i], str2[j+1] = '#';
        str2[j] = '\0';
    }
    
    int FindMaxPalindrome(char* str)
    {
        int iMax = 0, i;
        int p[MAXN*2], index = 0, mx = 0;
        memset(p, 0, sizeof(p));
        for(i = 1; str[i] != '\0'; ++i)
        {
            p[i] = mx > i ? MIN(p[2*index-i], mx-i) : 1;
            while(str[i+p[i]] == str[i-p[i]])
                p[i]++;
            if(i+p[i] > mx)
            {
                mx = p[i] + i;
                index = i;
            }
            if(p[i] > iMax)
                iMax = p[i];
        }
        return iMax-1;
    }
    
    int main()
    {
        char str1[MAXN], str2[2*MAXN];
        int iMax;
        while(scanf("%s", str1) != EOF)
        {
            AddSpecialChar(str1, str2);
            iMax = FindMaxPalindrome(str2);
            printf("%d\n", iMax);
            str1[0] = '\0';
            str2[0] = '\0';
        }
        return 0;
    }
    


    展开全文
  • 在hihoCoder上发现了比manacher更快的算法, 看上去很暴力,但跑起来蜜汁快,记录一下贴出来#include using namespace std;const int N = 1000000 + 10; char str[N]; int fast(char *str) { int ans = 0; str[0]...

    在hihoCoder上发现了比manacher更快的算法, 看上去很暴力,但跑起来蜜汁快,记录一下贴出来

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1000000 + 10;
    char str[N];
    int fast(char *str)
    {
        int ans = 0;
        str[0] = '?';
        for(int i = 0; str[i]; i++)
        {
            int s = i, e = i;
            while(str[e+1] == str[i]) ++e;
            i = e;
            while(str[s-1] == str[e+1]) --s, ++e;
            ans = max(ans, e - s + 1);
        }
        return ans;
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        while(n--)
        {
            scanf("%s", str + 1);
            printf("%d\n", fast(str));
        }
        return 0;
    }
    
    展开全文
  • 另外,求最大回文串(连续)的o(n)算法 马拉车算法 #include #include #include #define MAX_BUF 1024 #define MIN(a, b) ((a)<(b)?(a):(b)) int main(int argc, char *argv[]) { char ori_str[MAX_BUF]; ...
  • 宿舍的交换机坏了,因为之前还没开学,所以就没人修,然后就拖到现在寝室才有网。然后这几天因为省赛选拔赛所以心好累 /************************...s 字符原 str 通过在每两个数组元素之间添加’#’形成的新 p[i
  •  这道题意思是求最长回文字符,然后是连续递增的... 代码: 1 #include 2 #include< string .h> 3 #include 4 #define maxn 100002 5 int str[maxn 1 ]; 6 int ra[maxn 1 ]; 7 ...
  • hdu 3068 最长回文 (manacher算法) 1. 回文串定义 回文串是一个正读和反读都一样的字符串,比如“aba”或者“abba”等等就是回文串。 2. 最长回文子串方法 最长回文子串的长度方法可以有三种方法: 1) 朴素算法是...
  • Java基础算法之找出一段字符串中所有回文串、最长的回文串以及最长回文串长度 回文的含义是:字符串从左向右看和从右向左看是相同的,例如:abba,1234321。 单一字符亦是回文串 package ...
  • 参考博客:Manacher算法--O(n)回文子串算法 - xuanflyer - 博客频道 - CSDN.NET  从队友那里听来的一个算法,O(N)求得每个中心延伸...然后其中找最长回文串的操作其实还是暴力的,只不过这样记录两个位置以及覆...
  • Manacher算法,O(n)回文子串算法 ... 首先:大家都知道什么叫回文串吧,这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在O(n)的时间复杂度内既线性时间复杂度的情况下,求出以每个字符为中心
  • Manacher算法,俗称马拉车算法,是一种比较高效的回文串查找算法。 对于这个算法,我主要是从https://www.cnblogs.com/fan1-happy/p/11166182.html这篇博客中学习的,不过我觉得这篇文章太…应该说中二吧,反正我看...
  • 总结回文相关的算法题,判断是否是回文串,是否是回文数,最长回文串,回文串的个数等
  • 这算是个历史遗留问题了啊,当时没怎么看,最近又发现了,标记一下。脑子越来越不好使了啊。 Manacher算法:...最长回文 Time Limit: 4000/2000 MS (Java/Others
  • 求用这样的方法能得到的最长回文串的长度。注意:求的不是本质不同的回文串个数哦!!! 解题报告:找两个之间的最长回文串,只不过我卡了一下午而已,其实很简单,跑两遍马拉车,把两个字符串的len处理出来,开始...
  • 最长回文串——manacher算法java实现

    千次阅读 2017-08-09 10:23:51
    最长回文串是一个很好玩的话题,给出一个无序的不定长的字符序列,如何知道里面的最长回文串呢? manacher算法的思想是 把偶数、奇数长的字符序列变成奇数长度 创建一个与字符串等长的数组,用来记录字符序列相应...
  • 我们在平常做题的时候呢,有时候会遇到需要求最长回文串的要求,回文串就是从左读和从右读完全一样的字符串,如 aaaa , ababa, baab, 这样类型的字符串,我们初始的比较省时省力的方法呢,就是从中间往两边扩,但是...
  • 每日算法-最长回文串

    2020-03-19 22:20:09
    今日分享一个最长回文串算法,中等难度,只要想到方法,很容易就能写出一种算法。废话不多说,开搞。 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,178
精华内容 1,271
关键字:

最长回文串算法