程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3068 最長回文子串O(n)算法

HDU 3068 最長回文子串O(n)算法

編輯：C++入門知識

最長回文

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

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

4
3
以前沒有學過，最長的什麼什麼序列看來得重新學一下了，發現比賽的什麼水題可能會用得到來處理一下字符串啊什麼的。最長回文子串求法網址：http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063.html以前自己寫的求最長回文子串復雜度都太高，所以肯定會超時的，現在重新學重新用一下，哈哈。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 2200205
#define MN 105
#define INF 10000007
using namespace std;
int l,p[MM];
char s[MM>>1],str[MM];
void kp()
{
    int ans=0,id;
    for(int i=1;ii) p[i]=min(p[2*id-i],p[id]+id-i);
        else p[i]=1;
        for(;str[i+p[i]]==str[i-p[i]];p[i]++);
        if(p[i]+i>ans) ans=p[i]+i,id=i;
    }
}
void convert()
{
    int i,j,k;
    l=strlen(s);
    str[0]='$',str[1]='#';
    for(i=0;i
POJ 3974代碼：#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 2200205
#define MN 105
#define INF 10000007
using namespace std;
int l,p[MM],k;
char s[MM>>1],str[MM];
void kp()
{
    int ans=0,id;
    for(int i=1;ii) p[i]=min(p[2*id-i],p[id]+id-i);
        else p[i]=1;
        for(;str[i+p[i]]==str[i-p[i]];p[i]++);
        if(p[i]+i>ans) ans=p[i]+i,id=i;
    }
}
void convert()
{
    int i,j,k;
    l=strlen(s);
    str[0]='$',str[1]='#';
    for(i=0;i