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

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

2026-01-15 20:24:48

发布于：上海

389阅读

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

全部评论 30

AAA鋼筋批發金总
黑羊牛逼

2026-01-10 来自上海
4
- AAA鋼筋批發金总
  回复
  AAA鋼筋批發金总
  ddd
  
  2026-01-10 来自上海
  4
AAA鋼筋批發金总
ddd

2026-01-10 来自上海
4
Zzzzzzsr（不处）
挺好的，给两个建议

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

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

例子： $Manacher$ 中 $mx$ 更新时。
这句话应该改为
Manacher中 $mx$ 更新时。
或者
$\tt{Manacher}$ 中 $mx$ 更新时。
2026-01-08 来自广东
3
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  Zzzzzzsr（不处）
  谢谢，其实我是
  
  $\text{Manacher}$
  
  $\text{Manacher}$
  2026-01-08 来自上海
  2
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  Zzzzzzsr（不处）
  已修改
  
  2026-01-08 来自上海
  1
- 54188官方正版挂壁猴-π-人
  回复
  ༺ཌༀཉི༒白·羊༒༃ༀད༻
  $\tt{Manacher}$
  
  2026-01-10 来自浙江
  0
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

2026-01-04 来自上海
3
- AAA鋼筋批發金总
  回复
  ༺ཌༀཉི༒白·羊༒༃ༀད༻
  d
  
  2026-01-04 来自上海
  2
AAA鋼筋批發金总
d

2026-01-10 来自上海
2
༺ཉStars_Seekerད༻
ddd

2026-01-09 来自重庆
2
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  ༺ཉStars_Seekerད༻
  感谢支持
  
  2026-01-10 来自上海
  1
༺ཉStars_Seekerད༻
吓哭了
别说话，用心感受。。。

2026-01-09 来自重庆
2
AAA鋼筋批發金总
d

2026-01-04 来自上海
2
AAA鋼筋批發金总
d

2026-01-04 来自上海
2
Dog
你好陌生人，请问你生日是多少

2026-01-12 来自上海
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  Dog
  ？
  
  2026-01-12 来自上海
  0
AAA鋼筋批發金总
ddd

2026-01-11 来自上海
1
AAA鋼筋批發金总
d

2026-01-11 来自上海
1
AAA鋼筋批發金总
d

2026-01-11 来自上海
1
AAA鋼筋批發金总
d

2026-01-11 来自上海
1
AAA鋼筋批發金总
d

2026-01-11 来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
@沈思邈
 @AAA鋼筋批發金总

2026-01-07 来自上海
1
༺ཌༀཉི༒白·羊༒༃ༀད༻
d

2026-01-07 来自上海
1
AAA鋼筋批發金总
d

2026-01-04 来自上海
1
AC君
A：
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using PolyConvolution;
using StringManacher;
constexpr int N = 1e5 + 10, p = 1e9 + 7;
int n, m, pw[N], a[N << 1], ans;
char str[N]; std::vector<int> v;
int main(){
scanf("%s", str);
n = strlen(str), pw[0] = 1;
FL(i, 1, n) pw[i] = (pw[i - 1] << 1) % p;
auto C = [](int x){
v.resize(n);
FL(i, 0, n - 1) v[i] = (str[i] - 'a') ^ x;
auto t = Convolution(v, v);
FL(i, 0, (n - 1) * 2) a[i] += (int)round(t[i]);
};
C(0), C(1);
FL(i, 0, (n - 1) * 2){
ans = (ans + pw[(a[i] + 1) >> 1] - 1) % p;
}
printf("%lld\n", ((ans - Manacher(str)) % p + p) % p);
return 0;
}

1周前来自浙江
0
AC君
扩展题好简单，代码如下：
#include <bits/stdc++.h>
namespace Poly{
constexpr int N = 2.7e5 + 10;
constexpr double Pi = acos(-1);
int n, m, p[N];
stdcomplex<double> f[N], g[N];
void FFT(int n, stdcomplex<double> *c, int x = 1){
for(int i = 0; i < n; ++i) if(i < p[i]) stdswap(c[i], c[p[i]]);
for(int b = 2, k = 1; b <= n; b <<= 1, k <<= 1){
stdcomplex<double> t(cos(2 * Pi / b), sin(2 * Pi / b) * x), w(1, 0);
for(int i = 0; i < n; i += b, w = 1){
for(int j = 0; j < k; ++j, w *= t){
c[i + j] += c[i + j + k] * w;
c[i + j + k] = c[i + j] - c[i + j + k] * w - c[i + j + k] * w;
}
}
}
}
stdvector<double> Convolution(const auto &a, const auto &b){
if(!a.size() || !b.size()) return stdvector<double>();
n = a.size(), m = b.size();
int l = 1 << (int)ceil(log2(n + m - 1));
for(int i = 0; i < l; ++i){
f[i] = i < n? a[i] : 0, g[i] = i < m? b[i] : 0;
p[i] = (p[i >> 1] >> 1) | (i & 1? l >> 1 : 0);
}
n += m - 1, FFT(l, f), FFT(l, g);
for(int i = 0; i < l; ++i) f[i] *= g[i];
FFT(l, f, -1); stdvector<double> ret;
for(int i = 0; i < n; ++i)
ret.emplace_back(f[i].real() / l);
return ret;
}
}
namespace String{
constexpr int N = 1e5 + 10;
char s[N << 1]; int n, p[N << 1];
long long Manacher(char a[]){
int la = strlen(a);
s[n = 0] = '$', s[++n] = '#';
for(int i = 0; i < la; ++i) s[++n] = a[i], s[++n] = '#';
s[n + 1] = '%';
int m = 0, r = 0; long long ans = 0;
for(int i = 1; i <= n; ++i){
p[i] = (i <= r? stdmin(p[m * 2 - i], r - i + 1) : 1);
while(s[i - p[i]] == s[i + p[i]]) ++p[i];
if(i + p[i] - 1 > r) m = i, r = i + p[i] - 1;
ans += (p[i] >> 1);
}
return ans;
}
}
下面A接着发

1周前来自浙江
0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  AC君
  哥们你会FFT？我为了这道题去学了FFT
  
  1周前来自上海
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复
  AC君
  你放在代码块里发我下呗
  
  1周前来自上海
  0