最小表示法即寻找使循环串最小字典序的起始位置.

详见周源的ppt和http://www.chhaya.me/?p=229.

基本上就是两个指针i=0,j=1.从s[i]和s[j]开始比较第k个字符是否相同,当k==len时,返回i,j中的最小值.当s[i+k]和s[j+k]不相同时,若s[i+k]>s[j+k]则可见从s[i+1]到s[i+k]都不会是最小字典序的起始位置,所以i=i+k+1.当s[i+k]<s[j+k]时同理.若移动后i==j则使正在移动的那个指针++.然后从新的s[i]和s[j]开始比较.

#include <cstdio>
#include <cstring>

int mins(const char *s)
{
    int len=strlen(s);
    if(len==0||len==1) return 0;
    int i=0,j=1,k;
    char ci,cj;
    do
    {
        for(k=0;k<len;k++)
        {
            ci=s[(i+k)%len];
            cj=s[(j+k)%len];
            if(ci!=cj) break;
        }
        if(k==len) break;
        else if(ci>cj) 
        {
            i=i+k+1;
            if(i==j) i++;
        }
        else 
        {
            j=j+k+1;
            if(j==i) j++;
        }
    }while(1);
    return i<j?i:j;
}

char s[10001];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%s",s);
        printf("%d\n",mins(s)+1);
    }
}