【题目来源】
【题目描述】
若长度为 n 的字符串 s 中可以选择一个位置 i，使得 si…sns1·si-1=t，则称 s 与 t 循环同构。字符串 s 的最小表示为与 s 循环同构的所有字符串中字典序最小的字符串。
给定一个长度为 n 的字符串 s，请求出 s 的最小表示。
【输入格式】
第一行一个整数 n。
第二行一个长度为 n 的字符串 s。
【输出格式】
一行，一个字符串，为 s 的最小表示。
【输入样例】
10
caacabcaab
【输出样例】
aabcaacabc
【数据范围】
对于全部数据，1≤n≤10^7，字符串 s 仅包含小写英文字母（ASCII 97～122）。
设置以下三档部分分，用于测试不同解法：
● 对于 20% 的数据，n≤10^3；
● 对于 50% 的数据，n≤10^5；
● 对于 100% 的数据，无特殊限制。
【算法分析】
● 本题代码与“洛谷 P1368：工艺（）”基本一致。
● 本题是寻找字符串（或序列）最小表示的经典问题。
● 算法原理：利用数组倍增处理环形结构，或称之为解环成链，即将环形结构转为其 2 倍长度的线性结构。通过 while 循环进行双指针比较，i 和 j 分别代表当前竞争最小起始点的两个候选下标。当发现失配时，根据大小关系利用性质 i+=k+1 或 j+=k+1 快速跳过不可能成为答案的区间，从而实现线性扫描。最终输出从 min(i, j) 开始的 n 个元素。
【算法代码】
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const LL maxn=2e7+5;
char a[maxn];
int n;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=0; i<n; i++) {cin>>a[i];a[i+n]=a[i]; //auxiliary sequence of length 2n}int i=0,j=1; //Two starting positionsint k=0; //Indicates the offsetwhile(i<n && j<n && k<n) {if(a[i+k]==a[j+k]) k++;else {if(a[i+k]>a[j+k]) i+=k+1;else j+=k+1;if(i==j) i++;k=0;}}int p=min(i,j);for(int q=0; q<n; q++) {cout<<a[p+q];}return 0;
}/*
in:
10
caacabcaabout:
aabcaacabc
*/
【参考文献】