最小表示法学习笔记
title: 最小表示法学习笔记
categories:
- ICPC
tags:
- null
abbrlink: 2d46b897
date: 2023-12-27 00:00:00
最小表示法
有一个长度为 $n$的字符串 s,如果我们不断把它开头的字符移到结尾,可以得到 n个字符串,这些字符串是循环同构的,其中字典序最小的就是 s的最小表示。
string getmin(string s){
int len=s.size();
s+=s;
s=" "+s;
int i=1,j=2;//i,j表示以其位置开头的循环串
while(j<=len){
int k=0;//时间复杂度线性
while(k<len&&s[i+k]==s[j+k])k++;
if(s[i+k]>s[j+k]){
i+=k+1;
}
else j+=k+1;
if(i==j)j++;
if(i>j)swap(i,j);
}
//最终字典序最小的是以i开头的
return s.substr(i,len);
}
P1368 【模板】最小表示法
https://www.luogu.com.cn/problem/P1368
给一个数组,要求其循环同构串的字典序最小的.我们只需要改成vector就可以了。
vector<int>getmin(vector<int>s){
int len=s.size()-1;
for(int i=1;i<=len;i++)s.push_back(s[i]);
//for(auto x:s)cerr<<x<<" ";
int i=1,j=2;
while(j<=len){
int k=0;
while(k<len&&s[i+k]==s[j+k])k++;
if(s[i+k]>s[j+k]){
i+=k+1;
}
else j+=k+1;
if(i==j)j++;
if(i>j)swap(i,j);
}
vector<int>res;
for(int l=i;l<=i+len-1;l++)res.push_back(s[l]);
return res;
}
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
auto u=getmin(a);
for(auto x:u)cout<<x<<" ";
}
https://acm.hdu.edu.cn/showproblem.php?pid=7279
题意:给定n个串,每次查询两个串是不是循环右移串。如果存在整数 k,使得字符串 S 经过循环右移 k 个位置后变成字符串 T,那么字符串 S 和 T被称为循环右移串。
Sol:发现循环右移串就是同构串。我们需要预处理出n个串最小表示,然后就可以做到$O(1)$查询了。
void solve(){
cin>>n>>m;
vector<string>v(n+1);
vector<string>res(n+1);
for(int i=1;i<=n;i++){cin>>v[i];res[i]=getmin(v[i]);}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
if(res[x]==res[y])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
循环同构还有几种常见等价描述:
1.将字符串沿着某两个字母之间截断,分成两个子串,并将左子串放到右子串的后面,就可以形成一个新的字符串。
2.可以不断地把字符串首字母放到末尾,也就是左移。
kmp中可以知道最小循环覆盖的长度n-nx[n],考虑这么长的前缀一定是一个最小循环覆盖,所以现在求字典序最小的最小循环覆盖,只需要对着这个前缀getmin就可以。从理解上来说就是平移切割点
例题1
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!