首页 > 代码库 > Manacher模版

Manacher模版

2024-08-06 14:22:16   213人阅读

求字符串中出现过的最长回文子串

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. const int MAXN = 110010;  
  2. //字符串长度<MAXN  
  3. char Ma[MAXN * 2];  
  4. int Mp[MAXN * 2];  
  5. int Manacher(char s[]) {  
  6.     int l = 0, len = strlen(s);  
  7.     Ma[l++] = ‘$‘;  
  8.     Ma[l++] = ‘#‘;  
  9.     for (int i = 0; i<len; i++)  {  
  10.         Ma[l++] = s[i];  
  11.         Ma[l++] = ‘#‘;  
  12.     }  
  13.     Ma[l] = 0;  
  14.     int mx = 0, id = 0;  
  15.     for (int i = 0; i<l; i++)  {  
  16.         Mp[i] = mx>i ? min(Mp[2 * id - i], mx - i) : 1;  
  17.         while (Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++;  
  18.         if (i + Mp[i]>mx)   {  
  19.             mx = i + Mp[i];    id = i;  
  20.         }  
  21.     }  
  22.     int ans = 0;  
  23.     for (int i = 0; i<2 * len + 2; i++)  
  24.         ans = max(ans, Mp[i] - 1);  
  25.     return ans;  
  26. } 

Manacher模版


联系
我们