F01 最小表示法

#include<bits/stdc++.h>
using namespace std; 
char s[2110000];
int get_min(char *s, int len)
{
	for(int i=1;i<=len;i++) s[i+len]=s[i];
	int i=1,j=2,k=0;
	while(i<=len&&j<=len)//注意<=
	{
		for(k=0;k<len&&s[i+k]==s[j+k];k++);
		if(k==len) break;
		s[i+k]>s[j+k]?i=i+k+1:j=j+k+1;//设i<= i' <=i +k ，j<= j' <=j +k (i'-i=j'-j)，则 字符串(s[i']~s[i+k]) > 字符串(s[j']~s[j+k])
		if(i==j)j++;
	}
	return min(i,j);
}
int main()
{
	//freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	scanf("%s",s+1);
	int n=strlen(s+1);
	int p=get_min(s,n);
	for(int i=p;i<p+n;i++) printf("%c",s[i]);
	printf("\n"); 
	return 0;
}

使用$string$的做法

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s; cin >> s;
    int i = 1, j = 2, k = 0, n = s.size();
    s = ' ' + s + s;
    while (i <= n and j <= n)
    {
        for (k = 0; k <= n and s[i + k] == s[j + k]; k++);
        s[i + k] < s[j + k] ? j = j + k + 1 : i = i + k + 1;
        if (i == j) j++;
    }
    cout << s.substr(min(i, j), n);
    return 0;
}