#创作计划# 最小表示&Manacher

༺ཌༀཉི༒白·羊༒༃ༀད༻

2026-01-07 20:06:05

发布于：上海

17阅读

0回复

0点赞

字符串的70%可以用哈希+二分解决，而剩下30%中的70%可以用后缀数组解决

                                                                ——————༺ཌༀཉི༒白·羊༒༃ༀད༻

~~标题险些打不下~~

如你所见，本文讲解两种算法：最小表示法& $\text {Manacher}$ 算法（俗称马拉车）

Part 1.最小表示法

前置芝士：循环同构

定义：当字符串 $S$ 中可以选定一个位置 $i$ 满足

$S[i\cdots n]+S[1\cdots i-1]=T$

则称 $S$ 和 $T$ 循环同构

最小表示法

定义：字符串 $S$ 的最小表示为与 $S$ 循环同构的所有字符串中字典序最小的字符串。
人话：把 $S$ 放在一个环上，从任一点开始读取字符串，所得的串中字典序最小的即为 $S$ 的最小表示

暴力算法

思维难度：0
我们每次比较 $i$ 和 $j$ 开始的循环同构，把当前比较到的位置记作 $k$ ，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。

缺点
该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉。
例如：对于字符串 $aaa\cdots ab$ ，不难发现这个算法的复杂度退化为 $O(n^2)$

优化算法

我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程。
考虑字符串 $A$ 、 $B$ 为 $S$ 的两组循环同构，且他们的前 $k$ 个字符相等，即：

$S[i\cdots i+k-1]=S[j\cdots j+k-1]$

不妨设 $S[i+k]>S[j+k]$
如图，不难发现对于任意起始点为 $l(i\leq l\leq i+k)$ 的字符串均不可能成为答案（必定碰到红框导致被否掉）

（黑框部分为相等部分）

所以我们比较时可以跳过下标 $l\in [i,i+k]$ ，直接比较 $S_{i+k+1}$

算法流程

$(1)$ 初始化指针 $i=0,j=1$ ，匹配长度 $k=0$
$(2)$ 比较第 $k$ 位，根据比较结果跳转指针（哪个大跳哪个）。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同。
$(3)$ 重复 $(2)$ 直到结束
$(4)$ 从 $min(i,j)$ 开始输出答案
具体体细节见代码

例题1

板子题，直接上代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,s[3000009];
int init(){
    int i=0,j=1,k=0;
    while(i<n&&j<n&&k<n){
        int a=s[(i+k)%n+1],b=s[(j+k)%n+1];
        if(a==b)
            k++;
        else{
            if(a>b)
                i+=k+1;
            else
                j+=k+1;
            if(i==j)
                j++;
            k=0;
        } 
    }
    return min(i,j)+1; 
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    int k=init();
    for(int i=k;i<=n;i++)
        cout<<s[i]<<" ";
    for(int i=1;i<k;i++)
        cout<<s[i]<<" ";
    return 0;
}

例题2

还是板子题，直接把最小表示丢进set里
code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,len;
string s,s1;
set<string> se;
int init(string s){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int a=s[(i+k)%len+1],b=s[(j+k)%len+1];
        if(a==b)
            k++;
        else{
            if(a>b)
                i+=k+1;
            else
                j+=k+1;
            if(i==j)
                j++;
            k=0;
        } 
    }
    return min(i,j)+1; 
} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--){
        cin>>s;
        len=s.size();
        s=" "+s;
        int k=init(s);
        s1="";
        for(int i=k;i<=len;i++)
            s1+=s[i];
        for(int i=1;i<k;i++)
            s1+=s[i];
        se.insert(s1);
    }
    cout<<se.size();
    return 0;
}

Part 2.Manacher算法

引入

我们来看这样一个问题：求一个字符串的最长回文子串

暴力

非常简单，枚举每个子串，判断回文，时间复杂度 $O(n^3)$

中心扩展法

枚举每个点，向两边扩展，时间复杂度 $O(n^2)$
需要注意的是，这个算法只能判断奇数长度的回文
解决办法也很简单，在每个字符后面插入一个空格，把偶回文转换为奇回文

优化( $\text {Manacher}$ )

我们考虑以下定义
$p[i]$ ：表示以位置 $i$ 为中心的最大回文半径
$id$ ：当前已知的右边界最靠右的回文中心
$mx$ ：该回文的最右边界索引，满足 $mx=id+p[id]-1$

算法流程(具体细节见代码注释)

遍历每个位置 $i$ ，首先利用对称性确定 $p[i]$ 的初始值：
如果 $i$ 在当前最右回文边界 $mx$ 之外，只能从 $1$ 开始暴力扩展
如果 $i$ 在 $mx$ 之内，可以通过对称点 $i_1$ （ $i$ 关于 $id$ 的对称点）的信息，取 $min(mx-i, p[i_1])$ 作为初始值
确定初始值后，向两边扩展检查字符是否匹配，更新回文半径:
如果当前回文的右边界超过了 $mx$ ，则更新 $id$ 和 $mx$ 。

时间&空间复杂度

均为 $O(n)$ ，十分优秀

例题1

这道题的主要思路就是马拉车+快速幂
code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=19930726;
char s[1000009],str[2000009];
int p[2000009],cnt[1000009];
int len,n;
int ans=1,k;
int ksm(int x,int y){
    if(x==1)
        return 1;
    int res=1,xxx=x;
    while(y){
        if(y&1)
            res=(res*xxx)%mod;
        xxx=(xxx*xxx)%mod;
        y/=2;
    }
    return res;
}
void manacher(){
    for(int i=1;i<=len;i++)
        str[i*2-1]='%',str[i*2]=s[i];//特殊字符 
    str[len=len*2+1]='%';
    int id=0,mx=0;
    for(int i=1;i<=len;i++){
        if(i<mx)
            p[i]=min(p[id*2-i],mx-i);
        else
            p[i]=1;
        //p[i]初始值 
        while(p[i]+i<=len&&i-p[i]>=1&&str[i+p[i]]==str[i-p[i]])
            p[i]++;
        //中心扩展 
        if(p[i]+i>mx)
            id=i,mx=i+p[i];
        //更新右回文 
        if((p[i]-1)%2)
            cnt[p[i]-1]++;
        //统计奇回文 
    }
}
signed main(){
    int sum=0;
    cin>>n>>k>>s+1;
    len=n;
    manacher();
    for(int i=n;i>=1;i--){
        if(i%2==0)
            continue;//跳过偶回文 
        sum+=cnt[i];
        if(k>=sum){//k足够，i^sum 
            ans=(ans*ksm(i,sum))%mod;
            k-=sum;
        }
        else{//k不够，i^k 
            ans=(ans*ksm(i,k))%mod;
            k-=sum;
            break;
        }
    }
    if(k>0)
        ans=-1;
    cout<<ans;
    return 0;
}

例题2

这是一道比较难的题
先预告一下：这道题中有一个技巧：在原串中插入字符后再在头尾各插一个别的字符充当边界
接下来，题解开始：
我们处理出每个回文串的左右边界 $ll[i]$ 、 $rr[i]$
那么不难发现有：

$ll[i+p[i]−1]=max(ll[i+p[i]−1],p[i]−1)\\ rr[i−p[i]+1]=max(rr[i−p[i]+1],p[i]−1)$

（这段可以自己画画图）
跑完 $\text {Manacher}$ 后，我们求出每个'#'为断点的 $ll[i]$ 和 $rr[i]$ ，其中 $rr[i]$ 因为是 $i$ 结尾的回文长度，所以直接顺推，每往后移一位，最长回文子串长度− $2$ ，于是 $rr[i]=max(rr[i],rr[i−2]−2)$ (i−2是上一个'#'位置)，同理 $ll[i]$ 直接逆推： $ll[i]=max(ll[i],ll[i+2]−2)$

最后枚举每个'#'为断点，更新答案即可
code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int p[200009],ll[200009],ans,rr[200009],mx,id,cnt;
char s[10000009],t[10000009];
signed main(){
    cin>>t;
    int len=strlen(t);
    s[++cnt]='$',s[++cnt]='#';
    for(int i=0;i<len;i++)
        s[++cnt]=t[i],s[++cnt]='#';
    s[++cnt]='\0';
    for(int i=1;i<=cnt;i++){
        if(i<mx)
            p[i]=min(p[id*2-i],mx-i);
        else
            p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])
            p[i]++;
        if(mx<i+p[i])
            id=i,mx=i+p[i];
        ll[i+p[i]-1]=max(ll[i+p[i]-1],p[i]-1);
        rr[i-p[i]+1]=max(rr[i-p[i]+1],p[i]-1);
    }
    for(int i=2;i<=cnt;i+=2)
        rr[i]=max(rr[i],rr[i-2]-2);
    for(int i=cnt;i>=2;i-=2)
        ll[i]=max(ll[i],ll[i+2]-2);
    for(int i=2;i<=cnt;i+=2)
        if(rr[i]&&ll[i])
            ans=max(ans,ll[i]+rr[i]);
    cout<<ans;
    return 0;
}

*例题3

如你所见，这是一道紫题，~~吓哭了~~
但是我和题解区的一位大佬想到了同一个解法：
直接枚举一下每个处理出的回文是不是两段一样的回文相加不就好了？
具体实现：在 $\text {Manacher}$ 中 $mx$ 更新时,判断所有新出现的回文串的前一半是否为回文串即可。。。
然后就……
code:

#include<bits/stdc++.h>
using namespace std;
char s[1000010]={' '};
int p[1000010],n,ans;
void manacher(char *s,int n){
    for(int c=0,mx=0,i=1;i<=n;i++){
        if(i<mx)
            p[i]=min(p[2*c-i],mx-i);
        else
            p[i]=1;
        while(s[i+p[i]]==s[i-p[i]])
            ++p[i];
        if(i+p[i]>mx){
            if(i%2)
                for(int j=max(mx,i+4);j<i+p[i];j++)
                    if(!(j-i&3)&&p[i-(j-i)/2]>(j-i)/2)
                        ans=max(ans,j-i);
            mx=i+p[i],c=i;
        }
    }
}
int main(){
    cin>>n>>s+1;
    for(int i=n;i;i--)
        s[i*2+1]='#',s[i*2]=s[i];
    s[1]='#';
    manacher(s,2*n+1);
    cout<<ans;
    return 0;
}