最小表示法算法解析

提到最小表示法，要了解它的定义，最小表示法是用于解决字符串最小表示问题的方法。

一算法简介：

当一个字符串形成一个环的时候，要比较两个字符串是否相同就会变得很困难，因为你不知道对于第二个字符串来说，以哪个字符开始比较才会和第一个字符串相同。

所以我们就会想到枚举起点比较是否相同，而这样的复杂度O(n^2)。而最小表示法这种算法可以在O(n)的时间解决这个问题。下面介绍一下最小表示法。

二、算法分析：

1.首先将字符串S复制一份接在S的结尾，新的字符串称为字符串M。

2.我们假设现在正在比较分别以i，j为起点，比较i+k和j+k处的字符，前面小于k的字符已经匹配成功了。

此时发现M[i+k]>M[j+k]，那么很显然以i开头的字符串不是最小表示

而这也意味着另外一个问题，以i+1，i+2，……，i+k都不会是最小表示，因为无论以哪个位置为起点到M[i+k]这个位置时一定有更小的M[j+k]，所以之前的都不是答案。

同理可得M[i+k]<M[j+k]的情况，根据这个性质可以知道，所有的字符我们都只需要遍历一次，所以时间复杂度为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);//输出最小表示的起点
	
	return 0;
}