最小表示法

有一个长度为 $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