PTA A_1040 Longest Symmetric String

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805446102073344

解：
manacher算法

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int maxn = 1e3 + 10;
   
8. 
   
9. char a[maxn];
   
10. char b[maxn * 2];
    
11. int p[maxn * 2];
    
12. 
    
13. int init(char *a)
    
14. {
    
15. 
    
16.     b[0] = '!';
    
17.     b[1] = '#';
    
18. 
    
19.     int j = 2;
    
20. 
    
21.     for (int i = 0; i < strlen(a); ++i)
    
22.     {
    
23.         b[j++] = a[i];
    
24.         b[j++] = '#';
    
25.     }
    
26.     b[j] = '\0';
    
27. 
    
28.     return j;
    
29. }
    
30. 
    
31. int manacher(char *a)
    
32. {
    
33.     int len = init(a);
    
34.     int id = -1, mx = 0, ans = -1;
    
35. 
    
36.     for (int i = 1; i < len; ++i)
    
37.     {
    
38.         p[i] = (i < mx) ? min(p[2 * id - i], mx - i) : 1;
    
39.    
    
40.         while (b[i - p[i]] == b[i + p[i]]) ++p[i];
    
41. 
    
42.         if (i + p[i] > mx)
    
43.         {
    
44.             mx = i + p[i];
    
45.             id = i;
    
46.         }
    
47. 
    
48.         if (p[i] > ans) ans = p[i];
    
49.     }
    
50. 
    
51.     return ans - 1;
    
52. }
    
53. 
    
54. int main(void)
    
55. {
    
56.     // freopen("input.txt", "r", stdin);
    
57.     scanf("%[^\n]", a);
    
58. 
    
59.     printf("%d", manacher(a));
    
60. 
    
61.     return 0;
    
62. }

复制代码