程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3068 最長回文(Manacher)

HDU 3068 最長回文(Manacher)

編輯:C++入門知識

HDU 3068 最長回文(Manacher)


題意

給出一個只由小寫英文字符a,b,c…y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等

思路

用特殊字符插入到s串中每兩個字符中間,實現每個回文串都是奇數,再用manacher算法進行求解。

代碼

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 110009;
char s[N], t[N<<1];
int p[N<<1];

int manacher(int len)
{
    int id = 1, mx=0;
    p[0] = 1;
    for(int i=1; i i)
            p[i] = min(mx-i, p[2*id-i]);
        else
            p[i] = 1;
        while(t[i+p[i]] == t[i-p[i]])
            p[i]++;
        if(mx < p[i]+i)
        {
            mx = p[i]+i;
            id = i;
        }
    }
    int ans = p[1];
    for(int i=1; i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved