NOIP 普及 2012 第一轮 第 26 题：求字符串的字典序最小循环移位

题目

```
#include <iostream>
#include <string>
using namespace std;
int n,i,j,ans;
string s;
char get(int i)
{
	if(i<n) return s[i];
	else return s[i-n];	
}
int main()
{
	cin>>s;
	n=s.size();
	ans=0;
	for(i=1;i<=n-1;i++)
	{
		for(j=0;j<=n-1;j++)
			if(get(i+j)<get(ans+j))
			{
				ans=i;
				break;	
			}
			else if(get(i+j)>get(ans+j)) break;
	}
	for(j=0;j<=n-1;j++) cout<<get(ans+j);
	cout<<endl;
	return 0;	
}

```
输入：CBBADADA

阅读程序写结果

答案

ACBBADAD

题解

考点定位

字符串最小循环表示。

解题过程

实际输入为 CBBADADA，长度为 8。get 会把超过末尾的下标减去 n，从而读取循环串。程序逐一比较起点，保留字典序最小的循环移位。

最小串必以 A 开头，只需比较三个候选：

起点 7 的第二个字符是 C，另外两串第二个字符都是 D，且 C<D。因此最小串为 ACBBADAD。

答案：ACBBADAD。

易错提醒

最后一个字符也可以作为起点。程序从 1 枚举到 n−1，初始候选是 0，覆盖了全部 8 个起点。