Judging the longest palindrome string -- violence, extension, manacher

2021-01-23 21:10:35

1. violence

Time complexity O(n^3).

2. extension

Centered on a character , Set up left, right Two variables expand out at the same time , Determine if they point to the same character . Pay attention to the discussion of parity . Time complexity O(n^2).

3. Manacher A cart

code annotation ：

``` 1 const int MAXN = 110009;
2 char ma[MAXN * 2];   // Because to add '#', So it's twice the length
3 int mp[MAXN * 2];
4 char s[MAXN];
5
6 void Manacher(char s[], int len) {
7
8     // 1.  Construct string , add to '#', Make the length odd (2 * len - 1)
9     int l = 0;
10     ma[l++] = '\$';   //  Set boundaries
11     ma[l++] = '#';
12     for(int i = 0; i < len; i ++) {
13         ma[l++] = s[i];
14         ma[l++] = '#';
15     }
16     ma[l] = 0;
17
18     //  The core :  Finding palindrome radius ,  The palindrome radius includes the center point
19     int mx = 0; // mx Represents the rightmost value that can be reached
20     int id = 0; // id representative mx Center of
21     for(int i = 0; i < l; i ++) {
22         mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
23         while(ma[i + mp[i]] == ma[i - mp[i]]) {
24             mp[i] ++;
25         }
26         if(i + mp[i] > mx) {
27             mx = i + mp[i];
28             id = i;
29         }
30     }
31
32 }
33
34 int main()
35 {
36
37     while(scanf("%s", s) != EOF) {
38         int len = strlen(s);
39         Manacher(s, len);
40         int ans = 0;
41         for(int i = 0; i < 2 * len + 2; i ++) {   //  Find the longest palindrome radius , The length of palindrome string
42             ans = max(ans, mp[i] - 1);  //  Palindrome radius subtraction 1 Is the length of the original palindrome string ( In the palindrome radius, I added #)
43             cout << mp[i] << " ";
44         }
45         printf("%d\n", ans);
46     }
47
48     return 0;
49 }```

Time complexity O(n).

https://chowdera.com/2021/01/20210123210947242x.html