最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5158 Accepted Submission(s): 1755

Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

最长回文字串

一、暴力算法（O（n^3))

三个for循环

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

int main()

{

    char a[];

    int i,j,k,maxn=;

    cin>>a;

    for(int i=;a[i]!='\0';i++)

        a[i]=toupper(a[i]);

    int len=strlen(a);

    for(i=;i<len;i++)

    {

        for(j=i;j<len;j++)

        {

            int ok=;

            for(k=i;k<=j;k++)

            {

                if(a[k]!=a[i+j-k]) ok=;

            }

            if(ok)maxn=max(maxn,j-i+);

        }

    }

    cout<<maxn<<endl;

    return ;

}

二、优化算法（O(n^2))ps:分奇偶讨论

确定中心字符，两边扩展。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

int max(int a,int b){

    return a>b?a:b;

}

int main()

{

    char a[];

    int n;

    cin>>n;

    while(n--)

    {

        int i,j,maxn=,len;

        cin>>a;

        len=strlen(a);

        for(i=;i<len;i++)

        {

            for(j=;i-j>= && i+j<len;j++)

            {

                if(a[i-j]!=a[i+j]) break;

                else maxn=max(maxn,j*+);

            }

            for(j=;i-j>= && i+j+<len;j++)

            {

                if(a[i-j]!=a[i+j+]) break;

                else maxn=max(maxn,j*+);

            }

        }

        cout<<maxn<<endl;

    }

    return ;

}

三、manacher算法（O(n))ps:优化后的第二种算法

在第二种算法中，每次都确定中心字符两边扩展，并且分奇偶讨论，因此每次操作都会有不必要的操作，而manacher算法就是在每两个字符之间插入'#'字符，从而不需要分奇偶讨论。确定一个中心后，找上一个中心的标记点，标记点加上标记半径判断该点的初始回文状态即p[i]=min(p[id+id-i],p[id]+id-i].

然后在p[i]的基础上扩展当下点的标记半径。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

int p[];

char a[];

int main()

{

    while(cin>>a)

    {

        memset(p,,sizeof(p));

        int len=strlen(a),id=,maxlen=;

        for(int i=len;i>=;--i)

        {

            a[(i<<)+]='#';

            a[(i<<)+]=a[i];

        }
　　　　　a[0]='#';

        for(int i=;i<*len-;i++)

        {

            if(p[id]+id>i) p[i]=min(p[id*-i],p[id]+id-i);

            else p[i]=;

            while(a[i-p[i]]==a[i+p[i]]) ++p[i];

            if(id+p[id]<i+p[i])id=i;

            if(maxlen<p[i])maxlen=p[i];

        }

        cout<<maxlen-<<endl;

    }

    return ;

}

hihocode上的这道题就很简单了http://hihocoder.com/problemset/problem/1032

巴特西

最长回文子串 hihocode 1032 hdu 3068

最长回文

最新文章

热门文章