給出一個長度為N的字符串，求出它的最小表示。
算法是線性的，具體做法是設(shè)置兩個指針fst,sec。fst代表當(dāng)前找到的最小的字符串表示，sec表示下一個要匹配的初始位置。暴力的做法就是每次sec向后面移動一位o(N^2)的算法。線性的做法是根據(jù)前面的結(jié)果移動fst和sec。當(dāng)我們比較fst和sec形成的字符串的時候，有三種情況。第一種是比較到了第fst+len-1位和sec+len-1位置，相等。那么我們發(fā)現(xiàn)，fst和sec相等，不用多說,fst要移動到sec位置，sec移動到sec+1位置。這個比較明顯。然后是比較到第i位置的時候，str[fst+i] > str[ (sec + i )%len]，我們可以看到sec現(xiàn)在比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。好了，其實是比較明顯的一個算法，推一下就差不多了。第一次寫錯在了當(dāng)相等的時候直接返回了，汗。寫的還算干凈。
#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;
}