AcWing 158 项链 (最小表示法)

题目链接：https://www.acwing.com/problem/content/160/

最小表示法模板题

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 2000010;

int n, ans1, ans2;
char s1[maxn], s2[maxn], s3[maxn], s4[maxn];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	scanf("%s", s1 + 1); 
	scanf("%s", s2 + 1);
	n = strlen(s1 + 1);
	
	for(int i=1;i<=n;++i){ 
		s1[i + n] = s1[i];
		s2[i + n] = s2[i];
	} 
	
	int i = 1, j = 2, k;
	
	while(i <= n && j <= n){
		for(k=0; k<n && s1[i + k] == s1[j + k]; ++k);
		if(k == n) break;
		if(s1[i + k] > s1[j + k]){
			i = i + k + 1;
			if(i == j) ++i;
		} else {
			j = j + k + 1;
			if(i == j) ++j;
		}
	}
	
	ans1 = min(i, j);
	
	i = 1, j = 2;
	
	while(i <= n && j <= n){
		for(k=0; k<n && s2[i + k] == s2[j + k]; ++k);
		if(k == n) break;
		if(s2[i + k] > s2[j + k]){
			i = i + k + 1;
			if(i == j) ++i;
		} else {
			j = j + k + 1;
			if(i == j) ++j;
		}
	}
	
	ans2 = min(i, j);
	
	int len = 0;
	for(int i=ans1; i<=n; ++i) s3[++len] = s1[i];
	for(int i=1; i<ans1; ++i) s3[++len] = s1[i];
	
	len = 0;
	for(int i=ans2; i<=n; ++i) s4[++len] = s2[i];
	for(int i=1; i<ans2; ++i) s4[++len] = s2[i];
	
	int flag = 0;
	for(int i=1; i<=n; ++i){
		if(s3[i] != s4[i]){
			flag = 1;
			break;
		}
	}
	
	if(!flag){
		printf("Yes
");
		printf("%s
", s3 + 1);
	} else{
		printf("No
");
	}
	
	return 0;
}