数学之家

标题: 求回文串manacher算法 [打印本页]
作者: 低沉的游鱼    时间: 2014-6-17 22:25
标题: 求回文串manacher算法
本帖最后由 低沉的游鱼 于 2014-6-17 22:26 编辑

已被APIO题完虐，8分滚粗了。。于是我要下定决心好好学习。首先就学了一下manacher算法，T1要用到的算法

比如一个字符串abacaba，要求出里面所有的回文串。 如果回文串长度是奇数，就直接从中心向两边展开就行了。但如果是偶数呢？我们需要一个对这个字符串稍作变形。将这个字符串变为#a#b#a#c#a#b#a#。（#是一个辅助字符，要保证它在原串里不出现）。这样一来，原来长度是奇数的回文串长度还是奇数，长度为偶数的回文串就变成从其中一个#号展开。我们用p表示在这个新的字符串str中，以str为中心的最长回文串半径。这样一来，p-1表示的以str为中心的回文串在原串中的长度（很好证明，这里不多说）。

先贴一个完整的代码
  1. #include<iostream>  
  2. #include<cstring>  
  3. using namespace std;  
  4.   
  5. int manacher (char* s, int len)  
  6. {  
  7.     int nlen = 2 * len + 3;  
  8.     char* str = new char[nlen];      
  9.     int i = 0;
  10.     int max = 0;  
  11.     str[0] = ' ~';
  12.     str[1] = '#';  
  13.     for (; i < len; i++)  
  14.     {  
  15.         str[i * 2 + 2] = s[i];  
  16.         str[i * 2 + 3] = '#';  
  17.     }  
  18.     str[nlen - 1] = 0;  
  19.     int* p = new int[nlen];  
  20.   
  21.     for (int i = 1; i < nlen; i++)  
  22.     {  
  23.         p[i] = 0;  
  24.     }  
  25.   
  26.     int id = 0;  
  27.     for (i = 1; i < nlen; i++)  
  28.     {  
  29.         if (max > i)  
  30.             p[i] = min(p[2*id-i], max-i);  
  31.         else  
  32.             p[i] = 1;  
  33.         while (str[i+p[i]] == str[i-p[i]])  
  34.             p[i]++;  
  35.         if (p[i]+i > max)  
  36.         {  
  37.             max = p[i] + i;  
  38.             id = i;  
  39.         }  
  40.     }  
  41.   
  42.     int mx = 0;  
  43.     for (i = 1; i < nlen; i++)  
  44.     {  
  45.         if (mx < p[i] - 1)  
  46.             mx = p[i] - 1;  
  47.     }  
  48.     return mx;  
  49. }  
  50.   
  51. int main()  
  52. {  
  53.     char ch[100];  
  54.     while (cin >> ch)  
  55.     {  
  56.         cout << manacher(ch, strlen(ch)) << endl;  
  57.     }  
  58.     return 0;  
  59. }  
复制代码



这一句

if (max > i)  
            p = min(p[2*id-i], max-i);  

是整个算法中很重要的一个环节，利用了回文串的对称性，避免了许多不必要的计算。max表示的是之前的回文串匹配到的最远的位置，id保存的是这个回文串的i值。p[2*id-i]表示的就是i关于id对称的j的位置。但如果j的回文串长度较长，对称过来以后超出max的话，超出部分是还没有匹配的。因此，应该取的是两者之间较小值。

下图可能有助于理解



欢迎光临 数学之家 (http://www.2math.cn/) Powered by Discuz! X3.1