Manacher HDOJ 3068 最长回文-白红宇

Manacher HDOJ 3068 最长回文

阅读量：4516 次

发布时间：2019-06-08

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

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

1 int main(void)    { 2     while (scanf ("%s", str + 1) == 1)  { 3         int len = strlen (str + 1); 4         memset (dp, false, sizeof (dp)); 5         for (int i=1; i<=len; ++i)  dp[i][i] = true; 6         for (int i=1; i

n^2

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

1 waabwswfd2 pre: waabwswfd len: 93 now: $#w#a#a#b#w#s#w#f#d# len: 204 pi:  012123212121412121215 maxlen: 3

例子帮助理解

1 /* 2     题意：求最长回文串(不是) 3     Manasher：一个好理解，实现方便，O(n)时间复杂的很屌的算法。 4         简单说一下原理：首先将原字符串每个相邻之间插入一个不可能在字符串出现的字符，这样可以解决奇偶问题 5                         然后p[i]表示以i为回文中心，最长的回文长度(单边)，然而在原字符串中ans = max p[i] - 1 6                         我认为算法精髓在于求p[i]时充分利用了回文的性质，跳过了一些无用的扫描。如果不明白上面有例子 7     详细解释：     8 */ 9 /************************************************10 * Author        :Running_Time11 * Created Time  :2015-8-7 19:27:4612 * File Name     :Manacher.cpp13  ************************************************/14 15 #include 
     
      16 #include 
      
       17 #include 
       
        18 #include 
        
         19 #include 
         
          20 #include 
          
           21 #include 
           
            22 #include 
            
             23 #include 
             
              24 #include 
              
               25 #include 
               
                26 #include 
                
                 27 #include 
                 28 #include 
                  
                   29 #include 
                   
                    30 #include 
                    
                     31 #include 
                     
                      32 using namespace std;33 34 #define lson l, mid, rt << 135 #define rson mid + 1, r, rt << 1 | 136 typedef long long ll;37 const int MAXN = 1e5 + 10000;38 const int INF = 0x3f3f3f3f;39 const int MOD = 1e9 + 7;40 char s[MAXN], str[MAXN*2];41 int p[MAXN*2];42 43 int Manacher(void) {44 str[0] = '$'; str[1] = '#';45 int len = strlen (s);46 for (int i=0; i
                      
                        i) p[i] = min (p[2*id-i], mx - i);53 else p[i] = 1;54 while (str[i-p[i]] == str[i+p[i]]) p[i]++;55 if (mx < p[i] + i) {56 mx = p[i] + i; id = i;57 }58 }59 int ret = 0;60 for (int i=0; i