给出一个长度为N的字符串，求出它的最小表示。
算法是线性的，具体做法是设置两个指针fst,sec。fst代表当前找到的最小的字符串表示，sec表示下一个要匹配的初始位置。暴力的做法就是每次sec向后面移动一位o(N^2)的算法。线性的做法是根据前面的结果移动fst和sec。当我们比较fst和sec形成的字符串的时候，有三种情况。第一种是比较到了第fst+len-1位和sec+len-1位置，相等。那么我们发现，fst和sec相等，不用多说,fst要移动到sec位置，sec移动到sec+1位置。这个比较明显。然后是比较到第i位置的时候，str[fst+i] > str[ (sec + i )%len]，我们可以看到sec现在比fst小了，那么fst = sec, sec++。这也比较明显。然后是str[fst+i] < str[ (sec + i )%len]，这样，我们可以看到，以fst+k(k<i)的字符串和fst比，都比fst大，然后sec+i也比fst+i大，那么可知，sec到sec+i的那些玩意就不用再和fst比了，他们肯定比fst小。sec = sec+i+1。好了，其实是比较明显的一个算法，推一下就差不多了。第一次写错在了当相等的时候直接返回了，汗。写的还算干净。
#include <cstdio>#include <cstring>
const int maxn = 1001000;
char str[maxn];
int getans(int tlen)
{
int len = tlen;
int fst = 0,sec = 1,i;
while(sec < len)
{
for(i=0;i<len;i++)
{
if(str[fst+i] != str[(sec+i)%len])
break;
}
if(i == len)
{
fst = sec;
sec = sec + 1;
}
else if(str[fst+i] < str[(sec+i)%len])
{
sec = sec + i + 1;
}
else if(str[fst+i] > str[(sec+i)%len])
{
fst = sec;
sec = sec + 1;
}
}
return fst;
}
int main()
{
int tcase,tlen;
scanf("%d",&tcase);
while(tcase--)
{
scanf("%d%s",&tlen,str);
int ans = getans(tlen);
printf("%d\n",ans);
}
return 0;
}