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

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

2026-01-08 21:32:44

发布于：上海

151阅读

0回复

0点赞

upd1.8，更新了一道例题

$\tiny太好啦！加精啦！$

以下为正文。

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

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

~~标题险些打不下~~

如你所见，本文讲解两种算法：最小表示法& $\tt {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. $\tt Manacher$ 算法

引入

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

暴力

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

中心扩展法

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

优化( $\tt {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)$

（这段可以自己画画图）
跑完 $\tt {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

如你所见，这是一道紫题，~~吓哭了~~。
但是我和题解区的一位大佬想到了同一个解法：
直接枚举一下每个处理出的回文是不是两段一样的回文相加不就好了？
具体实现：在 $\tt {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;
}

嗯

例题4

这题洛谷上没找到，我觉得是紫
大致思路： $\tt Manacher$ +贪心区间覆盖
code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
char s[1000009],t[2000009];
int p[2000009];
int r[1000009];
void manacher(int n){
	for(int i=1;i<=n;i++){
		t[i*2-1]='#';
		t[i*2]=s[i];
	}
	t[n*2+1]='#';
	int m=n*2+1;
	int id=0,mx=0;
	for(int i=1;i<=m;i++){
		if(i<mx)
			p[i]=min(p[2*id-i],mx-i);
		else
			p[i]=1;
		while(i+p[i]<=m&&i-p[i]>=1&&t[i+p[i]]==t[i-p[i]])
			p[i]++;
		if(i+p[i]>mx){
			id=i;
			mx=i+p[i];
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string tmp;
	while(cin>>tmp){
		int n=tmp.length();
		for(int i=1;i<=n;i++)
			s[i]=tmp[i-1];
		manacher(n);
		for(int i=1;i<=n;i++)
			r[i]=i;
		for(int i=1;i<=n*2+1;i++){
			int len=p[i]-1;
			if(len<=0)
				continue;
			int ll,rr;
			if(i%2==0){
				int mid=i/2;
				ll=mid-len/2;
				rr=mid+len/2;
			}
			else{
				int mid=i/2;
				ll=mid-len/2+1;
				rr=mid+len/2;
			}
			if(ll>=1&&rr<=n){
				if(rr>r[ll])
					r[ll]=rr;
			}
		}	
		int cnt=0,now=0,nxt=0,pos=1;
		while(now<n){
			while(pos<=n&&pos<=now+1){
				if(r[pos]>nxt)
					nxt=r[pos];
				pos++;
			}
			if(nxt<=now)
				break;
			cnt++;
			now=nxt;
		}
		cout<<cnt-1<<endl;
	}
	return 0;
}

留道拓展题吧

~~你猜为啥是拓展题，因为我也不会~~。
~~谁做出来了私信一下我哈~~。
孩子们我们没救了！题解区怎么全是FFT啊吓哭了

完结撒花！

$\tiny 四蓝三紫，不知道要吓哭多少人$

有帮助，赞一个

去预览

0/2000

全部评论 20

复仇者_澜（不处不加团队）
挺好的，给两个建议

算法名不要直接加$符号 $Manacher$ ，可以写 Manacher 或者是 $\tt{Manacher}$ 。这里后者的写法是 $\tt{Manacher}$

对于加了$的东西，左右两边要空格。

例子： $Manacher$ 中 $mx$ 更新时。
这句话应该改为
Manacher中 $mx$ 更新时。
或者
$\tt{Manacher}$ 中 $mx$ 更新时。
2天前来自广东
3
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复复仇者_澜（不处不加团队）
  谢谢，其实我是
  
  $\text{Manacher}$
  
  $\text{Manacher}$
  2天前来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复复仇者_澜（不处不加团队）
  已修改
  
  2天前来自上海
  1
- 54188官方正版挂壁猴-π-人
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  $\tt{Manacher}$
  
  12小时前来自浙江
  0
AAA鋼筋批發金总
黑羊牛逼

15小时前来自上海
2
- AAA鋼筋批發金总
  回复AAA鋼筋批發金总
  ddd
  
  15小时前来自上海
  2
AAA鋼筋批發金总
ddd

15小时前来自上海
2
AAA鋼筋批發金总
d

15小时前来自上海
2
༺ཉStars_Seekerད༻
ddd

昨天来自重庆
2
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复༺ཉStars_Seekerད༻
  感谢支持
  
  21小时前来自上海
  1
༺ཉStars_Seekerད༻
吓哭了
别说话，用心感受。。。

昨天来自重庆
2
AAA鋼筋批發金总
d

6天前来自上海
2
AAA鋼筋批發金总
d

6天前来自上海
2
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

6天前来自上海
2
- AAA鋼筋批發金总
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  d
  
  6天前来自上海
  2
༺ཌༀཉི༒白·羊༒༃ༀད༻
@沈思邈
 @AAA鋼筋批發金总

3天前来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

3天前来自上海
1
AAA鋼筋批發金总
d

6天前来自上海
1
Xylophone
%%%本人极度讨厌字符串，但是想过考试，请问有什么做题建议吗

2天前来自广东
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Xylophone
  学好二分+哈希、马拉车、后缀数组、AC自动机、回文自动机
  
  昨天来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Xylophone
  呜呜呜我们最近全是字符串
  
  昨天来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Xylophone
  我建议你做一下那道拓展题
  
  昨天来自上海
  1
Xylophone
~~那我的九紫算什么~~

2天前来自广东
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Xylophone
  %%%
  
  昨天来自上海
  1
Xylophone
d

2天前来自广东
0
Xylophone
看了你的帖感觉自己是这个：

2天前来自广东
0
- Xylophone
  回复Xylophone
  
  2天前来自广东
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Xylophone
  什么意思？
  
  昨天来自上海
  1
- Xylophone
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  OI教练模拟器的图，第一张表示数据结构很强，第二张表示字符串很弱
  
  昨天来自广东
  0
MuktorFM
写的不错ddd

2天前来自云南
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复MuktorFM
  谢谢支持！
  
  2天前来自上海
  1
Gragher
哦不，不要AT我，thx

2天前来自浙江
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Gragher
  好的，挂你主页
  
  2天前来自上海
  1
Gragher
蒟蒻以严肃阅读后吓哭

3天前来自浙江
0
- Gragher
  回复Gragher
  其实还是不满足 $\LaTeX$ 格式规范但应该够了，起码有一定可读性，大部分加精帖子真的可读性一坨
  
  3天前来自浙江
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Gragher
  谢谢，我尽量完善一下 $\LaTeX$
  
  2天前来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Gragher
  已修改
  
  2天前来自上海
  1
咕咕咕
%%%

3天前来自江西
0