POJ 3974 Palindrome（最长回文子串）-白红宇

POJ 3974 Palindrome（最长回文子串）

阅读量：6978 次

发布时间：2019-06-27

本文共 1232 字，大约阅读时间需要 4 分钟。

题目链接：http://poj.org/problem?id=3974

题意：求一给定字符串最长回文子串的长度

思路：直接套模板manacher算法

code：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int MAXN = 1000010; 6 char Ma[2*MAXN]; 7 int Mp[2*MAXN]; 8  9 void Manacher(char s[], int len)10 {11     int l = 0;12     Ma[l++] = 'S';13     Ma[l++] = '#';14     for (int i = 0; i < len; ++i)15     {16         Ma[l++] = s[i];17         Ma[l++] = '#';18     }19     Ma[l] = 0;20     int mx = 0;21     int id = 0;22     for (int i = 0; i < l; ++i)23     {24         Mp[i] = mx > i ? min(Mp[2*id-i], mx-i) : 1;25         while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) ++Mp[i];26         if (i + Mp[i] > mx)27         {28             mx = i +Mp[i];29             id = i;30         }31     }32 }33 34 char s[MAXN];35 36 int main()37 {38     int cnt = 0;39     while (scanf("%s", s) != EOF)40     {41         if (strcmp(s, "END") == 0) break;42         int len = strlen(s);43         Manacher(s, len);44         int ans = 0;45         len = 2 * len + 2;46         for (int i = 0; i < len; ++i) ans = max(ans, Mp[i] - 1);47         printf("Case %d: %d\n",++cnt, ans);48     }49     return 0;50 }