最大最小表示法

给定一个字符串s，求与s循环同构的字符串中字典序最大/小的字符串。

比如s=“abc”，则与s循环同构的字符串有"abc", “bca”, “cab”

暴力的做法时间复杂度较高，而最大最小表示法的时间复杂度是O(n)

最大最小表示法

有两个指针i和j，初始时i=0, j=1，用k记录由i开头的字符串和由j开头的字符串的相同长度。

即s[i...i+k-1]==s[j...j+k-1]。

若由i开头的字符串和由j开头的字符串的第k+1个字符不相同，则面临两种情况，我们以最小表示法为例。

令t= s[(i+k)%n] - s[(j+k)%n]

若t>0，则表面i开头的第k+1个字符比由j开头的第k+1个字符大，则令i += k+1，即将i往后移，否则j += k+1。

为什么可以令i移动那么多呢？因为i与j相匹配的那些字符，都不可能是字典序最小的字符串的开头，下面证明一下为什么。

若s[i…i+k-1]与s[j…j+k-1]相匹配，且s[i+k] != s[j+k]。

若由i…i+k-1中的一个字符ii开头，则一定能在j…j+k-1中找到对应位置的jj，由jj开头的字典序一定比ii开头的要小，因为跑到s[i+k]和s[j+k]这个位置的时候，s[i+k]>s[j+k]。

比如当前由i开头的字符串是"abce"，由j开头的字符串是"abcd"，“abc"都能匹配上，但是"e”>“d”。

若由b开头，“bce"的字典序会大于"bcd”的字典序，所以某个位置失配的时候可以直接跳一大段。

最大表示法同理。

模板

返回的是以s[index]开头的字符串字典序最大/小的index

最小表示法

int getmin()
{
	int i=0, j=1, k=0, n=strlen(s);
	while(i<n && j<n && k<n)
	{
		int t = s[(i+k)%n]-s[(j+k)%n];
		if(!t)
			k++;
		else
		{
			if(t>0)
				i += k+1;
			else
				j += k+1;
			if(i==j)
				j++;
			k=0;
		}
	}
	return min(i, j);
}

最大表示法

int getmax()
{
	int i=0, j=1, k=0, n=strlen(s);
	while(i<n && j<n && k<n)
	{
		int t = s[(i+k)%n]-s[(j+k)%n];
		if(!t)
			k++;
		else
		{
			if(t<0)
				i += k+1;
			else
				j += k+1;
			if(i==j)
				j++;
			k=0;
		}
	}
	return min(i, j);
}