首页 > 代码库 > POJ (Manacher) Palindrome

POJ (Manacher) Palindrome

2024-07-18 06:39:07   221人阅读

多敲几个模板题，加深一下对Manacher算法的理解。

这道题给的时间限制15s，是我见过的最长的时间的了。看来是为了让一些比较朴素的求最大回文子串的算法也能A过去

Manacher算法毕竟给力，运行时间200+MS

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 1000000 + 100; 9 char s1[maxn], s2[maxn * 2];10 int p[maxn * 2];11 12 void Init(void)13 {14     s2[0] = ‘$‘, s2[1] = ‘#‘;15     int j = 2;16     for(int i = 0; s1[i] != ‘\0‘; ++i)17     {18         s2[j++] = s1[i];19         s2[j++] = ‘#‘;20     }21     s2[j] = ‘\0‘;22 }23 24 void manacher(char s[])25 {26     int id, mx = 0;27     p[0] = 0;28     for(int i = 1; s[i] != ‘\0‘; ++i)29     {30         if(mx > i)31             p[i] = min(p[id*2-i], mx-i);32         else33             p[i] = 1;34         while(s[i + p[i]] == s[i - p[i]])35             ++p[i];36         if(i + p[i] > mx)37         {38             mx = i + p[i];39             id = i;40         }41     }42 }43 44 int getans(void)45 {46     int ans = 1;47     for(int i = 1; s2[i] != ‘\0‘; ++i)48         ans = max(ans, p[i] - 1);49     return ans;50 }51 52 int main(void)53 {54     #ifdef LOCAL55         freopen("3974in.txt", "r", stdin);56     #endif57 58     int kase = 1;59     while(scanf("%s", s1) != EOF)60     {61         if(s1[0] == ‘E‘)    break;62         Init();63         manacher(s2);64         printf("Case %d: %d\n", kase++, getans());65     }66     return 0;67 }
代码君

 


联系
我们