首页 > 代码库 > POJ (Manacher) Palindrome
POJ (Manacher) Palindrome
多敲几个模板题,加深一下对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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。