给定一个字符串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);
}