L2-008 最长对称子串（25 分）

淡淡的烟草味﹌ 2022-05-24 02:04 158阅读 0赞

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAPsymmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。

**输入格式：**

输入在一行中给出长度不超过1000的非空字符串。

**输出格式：**

在一行中输出最长对称子串的长度。

**输入样例：**

Is PAT&TAP symmetric?

**输出样例：**

代码：

方法一：（暴力循环）

#include<stdio.h>
    #include<string.h>
    char str[1010];
    int main()
    {
        int i,j,n,m,k,t,l;
        gets(str);
        l=strlen(str);
        for(i=l;i>=2;i--)
        {
            for(j=0;j+i<l;j++)
            {
                for(k=j,t=j+i;k<=t;k++,t--)
                {
                    if(str[k]!=str[t])
                        break;
                }
                if(k>t)
                    break;
            }
            if(j+i<l)
                break;
        }
        if(i>=2)
        printf("%d",i+1);
        else
            printf("1");
        return 0;
    }

方法二：（manacher算法）

manacher算法:

定义数组p\[i\]表示以i为中心的(包含i这个字符)回文串半径长

将字符串s从前扫到后for(int i=0;i<strlen(s);++i)来计算p\[i\],则最大的p\[i\]就是最长回文串长度,则问题是如何去求p\[i\]?

由于s是从前扫到后的,所以需要计算p\[i\]时一定已经计算好了p\[1\]....p\[i-1\]

假设现在扫描到了i+k这个位置,现在需要计算p\[i+k\]

定义maxlen是i+k位置前所有回文串中能延伸到的最右端的位置,即maxlen=p\[i\]+i;//p\[i\]+i表示最大的

分两种情况:

1.i+k这个位置不在前面的任何回文串中,即i+k>maxlen,则初始化p\[i+k\]=1;//本身是回文串

然后p\[i+k\]左右延伸,即while(s\[i+k+p\[i+k\]\] == s\[i+k-p\[i+k\]\])++p\[i+k\]

2.i+k这个位置被前面以位置i为中心的回文串包含,即maxlen>i+k

这样的话p\[i+k\]就不是从1开始

由于回文串的性质,可知i+k这个位置关于i与i-k对称,

所以p\[i+k\]分为以下3种情况得出

//黑色是i的回文串范围,蓝色是i-k的回文串范围,

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

C代码:

#include<stdio.h>
    #include<string.h>
    char s[2010];
    int p[2010];
    int main()
    {
        gets(s);
        int len=strlen(s),id=0,maxlen=0;
        for(int i=len;i>=0;--i)
        {
            s[i+i+2]=s[i];
            s[i+i+1]='#';
        }
        s[0]='*';
        for(int i=2;i<2*len+1;++i)
        {
            if(p[id]+id>i)
                 p[i]=p[2*id-i]<p[id]+id-i?p[2*id-i]:p[id]+id-i;
            else
                 p[i]=1;
            while(s[i-p[i]] == s[i+p[i]])
                 ++p[i];
            if(id+p[id]<i+p[i])
                 id=i;
            if(maxlen<p[i])
                 maxlen=p[i];
        }
        printf("%d",maxlen-1);
        return 0;
    }

C++代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    using namespace std;
    string s;
    int p[2010];
    int main()
    {
        getline(cin,s);
        int len=s.length(),id=0,maxlen=0;
        for(int i=len;i>=0;--i)
        {
            s[i+i+2]=s[i];
            s[i+i+1]='#';
        }
        s[0]='*';
        for(int i=2;i<2*len+1;++i)
        {
            if(p[id]+id>i)
                 p[i]=p[2*id-i]<p[id]+id-i?p[2*id-i]:p[id]+id-i;
            else
                 p[i]=1;
            while(s[i-p[i]] == s[i+p[i]])
                 ++p[i];
            if(id+p[id]<i+p[i])
                 id=i;
            if(maxlen<p[i])
                 maxlen=p[i];
        }
        printf("%d\n",maxlen-1);
        return 0;
    }

[SouthEast]: /images/20220524/407f93b51b1743ef8b9c931dfe1799e6.png
[SouthEast 1]: /images/20220524/cd966fe6b12145aeb8c143fa07ecd34e.png
[SouthEast 2]: /images/20220524/131bf9e16db144d9a7c4df98698fd6b8.png
[SouthEast 3]: /images/20220524/0bca71d57e52463f86dd235205173790.png