当前位置:网站首页>Judging the longest palindrome string -- violence, extension, manacher

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

2021-01-23 21:10:35 Daybreaking

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).

版权声明
本文为[Daybreaking]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210123210947242x.html

随机推荐