Manacher HDOJ 3068 最长回文

题目传送门

关于求解最长回文子串，有dp做法，也有同样n^2的但只用O(1)的空间，还有KMP，后缀数组？？

 int main(void)    {

     while (scanf ("%s", str + ) == )  {

         int len = strlen (str + );

         memset (dp, false, sizeof (dp));

         for (int i=; i<=len; ++i)  dp[i][i] = true;

         for (int i=; i<len; ++i)   {

             dp[i][i+] = (str[i] == str[i+]);

         }

         int ans = ;

         for (int i=; i<=len; ++i)  {

             for (int j=; j+i-<=len; ++j)  {

                 if (dp[j+][j+i-] && str[j] == str[j+i-]) {

                     dp[j][j+i-] = true;

                     ans = max (ans, i);

                 }

             }

         }

         printf ("%d\n", ans);

     }

     return ;

 }

n^2

但是n^2的复杂度是过不了3068这题，下面用O(n)的算法解决

 waabwswfd

 pre: waabwswfd len:

 now: $#w#a#a#b#w#s#w#f#d# len:

 pi:

 maxlen: 

例子帮助理解

 /*

     题意：求最长回文串(不是最长回文子序列)

     Manasher：一个好理解，实现方便，O(n)时间复杂的很屌的算法。

         简单说一下原理：首先将原字符串每个相邻之间插入一个不可能在字符串出现的字符，这样可以解决奇偶问题

                         然后p[i]表示以i为回文中心，最长的回文长度(单边)，然而在原字符串中ans = max p[i] - 1

                         我认为算法精髓在于求p[i]时充分利用了回文的性质，跳过了一些无用的扫描。如果不明白上面有例子

     详细解释：中文版    英文版 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-7 19:27:46

 * File Name     :Manacher.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 char s[MAXN], str[MAXN*];

 int p[MAXN*];

 int Manacher(void)  {

     str[] = '$';  str[] = '#';

     int len = strlen (s);

     for (int i=; i<len; ++i)   {

         str[i*+] = s[i];  str[i*+] = '#';

     }

     len = len *  + ;  str[len] = '\0';

     int mx = , id = ;

     for (int i=; i<len; ++i)   {

         if (mx > i) p[i] = min (p[*id-i], mx - i);

         else    p[i] = ;

         while (str[i-p[i]] == str[i+p[i]])  p[i]++;

         if (mx < p[i] + i)  {

             mx = p[i] + i;  id = i;

         }

     }

     int ret = ;

     for (int i=; i<len; ++i)   {

         ret = max (ret, p[i]);

     }

     return ret - ;

 }

 int main(void)    {     //HDOJ 3068 最长回文

     while (scanf ("%s", s) == )  {

         printf ("%d\n", Manacher ());

     }

     return ;

 }