电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: Manacher算法 [打印本页]

作者: look_w 时间: 2019-2-19 15:48 标题: Manacher算法

最长回文子串问题#

给定一个字符串，找出最长的回文子串，如"waabwswbfd",则最长子串为bwsb.
中心试探法#

最简单的方法，将每一个字符当成中心点，向两边扩展，找到最长的。
时间复杂度为O（n^2）,太慢。
Manacher算法#

这个算法充分利用了字符串匹配问题的特殊性，大大减少了匹配次数，时间复杂度O(n)。
首先算法为了解决字符匹配中的奇偶问题，在每个字符之间插入了一个特别字符‘#’（字符串中不存在就可以）。并且为了数组不越界在首字符处插入了‘$’字符，原因在看完代码后自行思考。
改造后的数组如下：
"$#w#a#a#b#w#s#w#b#f#d#"
算法的关键在于使用了两个变量（也可以用一个变量），id和mx以及一个数组P。id为到i为止以每个字符为中心点的子串能匹配到的最长的一个中心点坐标。P[id]表示到当前为止可以向右的最长距离。mx为P[id] + id即到目前为止可以向右的最远的边界。
根据上面这三个值，有一个重要的结论，即当mx > i时P[i]>=min(P[2id - i], mx - i).
上面这个公式看起来很费解，下面分析一下。
令j = 2id - i；找个例子画一下其实j指的位置是以id为中心点i所对应的位置（就是以id为中心点折叠过去的位置），当mx>i时候说明之前有一个位置以id的中心点的回文子串向右可以越过当前位置i,那么这个子串向左也一定包含对应点j，因为回文是对称的，如果以j为中心点的回文子串被完全包含在以id为中心点的回文子串中，那么以i为中心点的回文子串的长度最少是P[j]的长度。如果没有完全包含，即P[j]>mx-i那么位置在mx以外的字符由于还没匹配到，所以是未知的，只能等匹配到了才能知道是否为回文。
所以可以得到如上的公式。可以看出在这其中mx是必然递增的，即不会回溯。

#include<vector>
#include<iostream>
using namespace std;

const int N=300010;
int n, p[N];
char s[N], str[N];

#define _min(x, y) ((x)<(y)?(x)

y))

void kp()
{
      int i;
      int mx = 0;
      int id;
      for(i=n; str[i]!=0; i++)
         str[i] = 0; //Ã»ÓÐÕâÒ»¾äÓÐÎÊÌâ¡£¡£¾Í¹ý²»ÁËural1297£¬±ÈÈçÊý¾Ý£ºababa aba
      for(i=1; i<n; i++)
      {
         if( mx > i )
            p[i] = _min( p[2*id-i], p[id]+id-i );
         else
            p[i] = 1;
         for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
            ;
         if( p[i] + i > mx )
         {
            mx = p[i] + i;
            id = i;
         }
      }
}

void init()
{
   int i, j, k;
   str[0] = '$';
   str[1] = '#';
   for(i=0; i<n; i++)
   {
   str[i*2+2] = s[i];
   str[i*2+3] = '#';
   }
   n = n*2+2;
   s[n] = 0;
}

int main()
{
   int i, ans;
   while(scanf("%s", s)!=EOF)
   {
   n = strlen(s);
   init();
   kp();
   ans = 0;
   for(i=0; i<n; i++)
   if(p[i]>ans)
      ans = p[i];
   printf("%d\n", ans-1);
   }
   return 0;
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)