提到最小表示法，要了解它的定義，最小表示法是用于解決字符串最小表示問(wèn)題的方法。

一算法簡(jiǎn)介：

當(dāng)一個(gè)字符串形成一個(gè)環(huán)的時(shí)候，要比較兩個(gè)字符串是否相同就會(huì)變得很困難，因?yàn)槟悴恢缹?duì)于第二個(gè)字符串來(lái)說(shuō)，以哪個(gè)字符開始比較才會(huì)和第一個(gè)字符串相同。

所以我們就會(huì)想到枚舉起點(diǎn)比較是否相同，而這樣的復(fù)雜度O(n^2)。而最小表示法這種算法可以在O(n)的時(shí)間解決這個(gè)問(wèn)題。下面介紹一下最小表示法。

二、算法分析：

1.首先將字符串S復(fù)制一份接在S的結(jié)尾，新的字符串稱為字符串M。

2.我們假設(shè)現(xiàn)在正在比較分別以i，j為起點(diǎn)，比較i+k和j+k處的字符，前面小于k的字符已經(jīng)匹配成功了。

此時(shí)發(fā)現(xiàn)M[i+k]>M[j+k]，那么很顯然以i開頭的字符串不是最小表示

而這也意味著另外一個(gè)問(wèn)題，以i+1，i+2，……，i+k都不會(huì)是最小表示，因?yàn)闊o(wú)論以哪個(gè)位置為起點(diǎn)到M[i+k]這個(gè)位置時(shí)一定有更小的M[j+k]，所以之前的都不是答案。

同理可得M[i+k]<M[j+k]的情況，根據(jù)這個(gè)性質(zhì)可以知道，所有的字符我們都只需要遍歷一次，所以時(shí)間復(fù)雜度為O(n)。

三、模板程序

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>

using namespace std;
typedef long long ll;
ll n,ans;
char s[10010];
void zuixiao()
{
	ll n=strlen(s+1);
	for(ll i=1;i<=n;i++)
		s[i+n]=s[i];
	ll i=1,j=2,k;
	while(i<=n && j<=n)
	{
		for(k=0;k<=n && s[i+k]==s[j+k];k++)
			;
		if(k==n)
			break;
		if(s[i+k]>s[j+k])
		{
			i=i+k+1;
			if(i==j)
				i++;
		}
		else
		{
			j=j+k+1;
			if(i==j)
				j++;
		}
	}
	ans=min(i,j);
}
int main()
{
	scanf("%s",s+1);
	zuixiao();
	printf("%lld",ans);//輸出最小表示的起點(diǎn)
	
	return 0;
}