题目背景
原模板题：P1368 工艺。
题目描述
若长度为 \(n\) 的字符串 \(s\) 中可以选择一个位置 \(i\)，使得 \(\overline{s_i\cdots s_ns_1\cdots s_{i-1}}=t\)，则称 \(s\) 与 \(t\) 循环同构。字符串 \(s\) 的最小表示为与 \(s\) 循环同构的所有字符串中字典序最小的字符串。
给定一个长度为 \(n\) 的字符串 \(s\)，请求出 \(s\) 的最小表示。
输入格式
第一行一个整数 \(n\)。
第二行一个长度为 \(n\) 的字符串 \(s\)。
输出格式
一行，一个字符串，为 \(s\) 的最小表示。
输入输出样例 #1
输入 #1
10
caacabcaab
输出 #1
aabcaacabc
说明/提示
对于全部数据，\(1\le n\le 10^7\)，字符串 \(s\) 仅包含小写英文字母（ASCII \(97\sim 122\)）。
设置以下三档部分分，用于测试不同解法：
- 对于 \(20\%\) 的数据，\(n\le 10^3\)；
- 对于 \(50\%\) 的数据，\(n\le 10^5\)；
- 对于 \(100\%\) 的数据，无特殊限制。
思路
首先破环成链，将字符串复制一倍。
设置两个指针，\(i\) ，\(j\) 来表示对比的循环字符串的起点，\(k\)表示此时对比的位数是第\(k\)位。
那么会出现三种情况，若 \(s[i+k]==s[j+k]\) 那么 \(k++\) ，如果 \(s[i+k]>s[j+k]\) 那么i就移动到i+k+1的位置上，同理若 \(s[i+k]<s[j+k]\) ，那么j就移动到 \(j+k+1\) 的位置上。
为什么这么做是可以的呢，以 \(s[i+k]>s[j+k]\) 来说明，因为当i，j位置发生移动的时候，就说明有 \(s[i]到s[i+k-1]\) 的区间与 \(s[j]\) 到 \(s[j+k]\) 的区间是一样的，下一位以 \(j\)开头更优，因此以i~i+k-1的区间作为开头的同时，j ~ j+k-1 的区间作为开头更优，因为到达 \(j+k\) 这一位的时候，这些区间内做开头显然都是j更优秀，所以可以直接跳过这段区间作为开头。
时间复杂度O(n)
题解
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n;void solve()
{ cin>>n;string s;cin>>s;s = s+s;// cout<<s<<endl;int k = 0;int j=1,i=0;while(i<n&&j<n){ for(k=0;k<n&&s[i+k]==s[j+k];k++);if(s[i+k]>s[j+k])i = i+k+1;else j = j+k+1;if(i==j)j++;}int st = min(i,j);for(int i=st;i<st+n;i++)cout<<s[i];cout<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}return 0;
}