hihoCoder1032 : 最长回文子串【manacher】

大意：求最长回文字串：

分析：

1、暴力方法。。枚举头尾，判断是不是回文串 0(n^3)

3、寻找中点往两边暴力 n^2

代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 55;
 7 
 8 char str[maxn];
 9 int main() {
10     int n;
11     while(EOF != scanf("%d",&n)) {
12         scanf("
%s",str);
13         int len = strlen(str);
14         int MaxLen = 1;
15         for(int i = 0; i < len; i++) {
16             int j = i - 1, k = i + 1;
17             while(j >= 0 && k < len && str[j] == str[k]) {
18                 j--; k++;
19             }
20             MaxLen = max(MaxLen, k - j - 1);
21             if(i < len - 1 && str[i] == str[i + 1]) {
22                 j = i - 1; k = i + 2;
23                 while(j >= 0 && k < len && str[j] == str[k]) {
24                     j--; k++;
25                 }
26                 MaxLen = max(MaxLen, k - j - 1);
27             }
28         }
29         printf("%d
", MaxLen);
30     }
31 }

View Code

2、dp dp[i][j] = 1 代表 i -- j 为回文串 0表示不是那么 dp[i][j] = dp[i + 1][j-1] (s[i] == s[j]) dp[i][j] = 0 (s[i] != s[j])

所以只要预处理出来每个字符和连续两个字符的然后枚举长度

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 55;
 7 
 8 int dp[maxn][maxn];
 9 
10 char str[maxn];
11 
12 int main() {
13     int n;
14     while(EOF != scanf("%d",&n)){
15         scanf("
%s",str);
16         int len = strlen(str);
17         memset(dp, 0, sizeof(dp));
18         int MaxLen = 1;
19         for(int i = 0; i < len; i++) {
20             dp[i][i] = 1;
21             if(i < len - 1 && str[i] == str[i + 1]) {
22                 dp[i][i + 1] = 1;
23                 MaxLen = 2;
24             }
25         }
26         for(int l = 2; l < len; l++) {
27             for(int i = 0; i < len; i++) {
28                 int j = i + l;
29                 if(j < len) {
30                     if(str[i] == str[j]) {
31                         dp[i][j] = dp[i + 1][j - 1];
32                         if(dp[i][j] == 1) {
33                             MaxLen = max(MaxLen, l + 1);
34                         }
35                     }
36                 }
37             }
38         }
39         printf("%d
", MaxLen);
40     }
41     return 0;
42 }

View Code

3、 O(n)的manacher算法

http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

讲的很细致

代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int maxn = 1000005 << 1;
 7 
 8 void manacher(char *str, int p[maxn]) {
 9     int len = strlen(str);
10     for(int i = len - 1; i >= 0; i--) {
11         str[i << 1 | 1] = '#';
12         str[(i + 1) << 1] = str[i];
13     }
14     str[0] = '$';
15     str[len << 1 | 1] = '#';
16     str[(len + 1) << 1] = 0;
17     int id = 0;
18     for(int i = 0; str[i]; i++) {
19         if(id + p[id] > i) {
20             p[i] = min(p[id * 2 - i], id + p[id] - i);
21         } else {
22             p[i] = 1;
23         }
24         while(str[i + p[i]] == str[i - p[i]]) p[i]++;
25         if(i + p[i] > id + p[id]) {
26             id = i;
27         }
28     }
29 }
30 
31 char str[maxn];
32 int p[maxn];
33 int main() {
34     int n;
35     scanf("%d",&n);
36     while(n--) {
37         scanf("
%s",str);
38         manacher(str,p);
39         int Max = 0;
40         for(int i = 0; str[i]; i++) {
41             Max = max(Max, p[i] - 1);
42         }
43         printf("%d
",Max);
44     }
45 }

View Code