【笔记】字符串::Manacher算法

这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战.

参考链接和图片来源：oi-wiki.org/string/mana…

简介

Manacher算法俗称马拉车，由Glenn K. Manacher在1975年提出，可以找到每个以字符位置或字符之间位置为中心的回文串长度。

因为回文串可以以两个字符间的位置作为中心，我们把原字符串两端及每两个字符之间插入一个不会被用到的字符，比如abababb变成#a#b#a#b#a#b#b#。

此时计算以每个字符位置

i为中心的回文串数量

d[i]，它同时也是原串中以其为中心的最长回文串长度 +1。
【例子】

# a # b # a # b # a # b # b #
1 2 1 4 1 6 1 6 1 4 1 2 3 2 1

  a   b   a   b   a   b   b
  1 0 3 0 5 0 5 0 3 0 1 2 1
复制代码

算法

首先按上述方法扩展字符串，然后只需要求得

d[i]数组。
朴素方法是以每个位置为中心开始不断扩展，直到停下为止，复杂度

O(n2)

为了快速计算，我们需要维护已找到的回文子串

[l,r]中最靠右的一个，即

r最大的一个。

1. 从
   $0$

   0到

   $n-1$

   n−1开始不断循环

   $i$

   i，按如下方法逐个计算

   $d[i]$

   d[i]：

2. 如果
   $i$

   i位于当前回文串之外，即

   $i>r$

   i>r，那么使用朴素算法从

   $1$

   1开始逐步扩展

   $d[i]$

   d[i]，停下后更新

   $(l,r),l=i-d[i]+1,r=i+d[i]-1$

   (l,r),l=i−d[i]+1,r=i+d[i]−1。

3. 如果
   $i<=r$

   i<=r，显然

   $l<=i<=r$

   l<=i<=r，此时可以找到

   $i$

   i在

   $(l,r)$

   (l,r)内的对称位置

   $j=r+l-i$

   j=r+l−i，此时分为两种情况：

   1. 如果
      $j-d[j]+1>l$

      j−d[j]+1>l，那么

      $i+d[j]+1<r$

      i+d[j]+1<r，此时因为

      $i$

      i和

      $j$

      j在

      $(l,r)$

      (l,r)内的对称性，可以断定

      $d[i]=d[j]$

      d[i]=d[j]。

2. 如果

j−d[j]+1<=l，那么

i+d[j]+1>=r，我们不能知道以

i为中心是否有更长的回文串在(l,r)之外：
在这种情况下，令

d[i]=r−i，然后使用朴素算法扩展。扩展完毕后需要更新

(l,r)

复杂度分析

每一步，要么

i增加，要么

r增加，这两者永不减少且最大为

n，所以复杂度

O(n)。

代码

char str[M], s[M];
int d[M]; //d[i]以i为中心的回文串个数，也表示原串中i/2+1位置为中心的最长回文串长度+1
int manacher(char *str) //处理字符串，得到d数组，返回最长回文子串的长度
{
    s[0] = '#';
    for(int i=0; str[i]; ++i)
    {
        s[i*2+1] = str[i];
        s[i*2+2] = '#';
    }
    for(int i=0, l=0, r=0; s[i]; ++i)
    {
        d[i] = 1;
        if(i<r) d[i] = min(d[l+r-i],r-i+1);
        while(i-d[i]>=0 && s[i+d[i]] && s[i-d[i]]==s[i+d[i]])
            ++d[i];
        if(i+d[i]-1>r)
        {
            r = i+d[i]-1;
            l = i-d[i]+1;
        }
    }
    int res = 1;
    for(int i=0; s[i]; ++i)
        res = max(res, d[i]-1);
    return res;
}
复制代码

习题

P3805 【模板】manacher算法
给定一个长度不超过11000000的字符串，求最长回文子串的长度。

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 23000016, MOD = 1000000007;

char str[M], s[M];
int d[M]; //d[i]表示i位置的
//也表示原串中i/2+1位置为中心的最长回文串长度+1
int manacher(char *str) //处理字符串，得到d数组，返回最长回文子串的长度
{
    s[0] = '#';
    for(int i=0; str[i]; ++i)
    {
        s[i*2+1] = str[i];
        s[i*2+2] = '#';
    }
    for(int i=0, l=0, r=0; s[i]; ++i)
    {
        d[i] = 1;
        if(i<r) d[i] = min(d[l+r-i],r-i+1);
        while(i-d[i]>=0 && s[i+d[i]] && s[i-d[i]]==s[i+d[i]])
            ++d[i];
        if(i+d[i]-1>r)
        {
            r = i+d[i]-1;
            l = i-d[i]+1;
        }
    }
    int res = 1;
    for(int i=0; s[i]; ++i)
        res = max(res, d[i]-1);
    return res;
}
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

    scanf("%s",str);
	int res = manacher(str);
    printf("%d\n",res );
    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
复制代码

--- 本文也发表于我的 csdn 博客中。