请选择 进入手机版 | 继续访问电脑版

数学之家

建站
数学爱好者的家园
 找回密码
 注册

QQ登录

只需一步,快速开始

查看: 1444|回复: 0

求回文串manacher算法

[复制链接]
发表于 2014-6-17 22:25:41 | 显示全部楼层 |阅读模式
本帖最后由 低沉的游鱼 于 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的话,超出部分是还没有匹配的。因此,应该取的是两者之间较小值。

下图可能有助于理解
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|网站统计|手机版|小黑屋|数学之家    

GMT+8, 2024-3-28 19:36 , Processed in 1.109383 second(s), 20 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表