什么是最小表示法呢?例如abcde 可以通过末尾的那位退到开头其他位往后移一步得到的形式就有五种如下:

 abcde
 bcdea
 cdeab
 deabc
 eabcd

其中字典序最小的就是abcde..那给定一个字符串我们如何ON求最小表示法呢?
首先复制一次把abcde变成abcdeabcde然后我们用两个指针i,j进行模拟.怎么模拟呢?其实还是比较简单的,拿两个指针作为以i位子开头和以j位子开头的表示最小.再拿k进行移动.我们假设当前位子相同对吧,那么我再用k表示剩下的位子是不是相同?假如相同就k++.有件东西是已知的,假如它们开始相同那么选择后面那个数小的会更优,因为下面无论怎么造,后面小的数造造出来的会更小.假如不同,那么大的数一定不会选.由此可以得到当一个数比较超过了限制,那么另一个数就是最小表示了.
伪代码如下.

void getmin(int a[])
{
    for(int i=0;i<2*n;i++) b[i]=a[i%n];
    int i=0,j=1,k;
    while(i<n&&j<n)
    {
        for(k=0;k<=n&&a[i+k]==a[j+k];k++);
        if(a[i+k]>a[j+k]) {i+=k+1;if(i==j) i++;}
        else              {j+=k+1;if(i==j) j++;}
    }
    int pos=min(i,j);
    for(int p=0;p<n;p++) a[p]=b[p+pos];
}

emm,讲完了