赤裸裸的字符串最小表示題。所謂字符串最小表示指的是給定一個字符串，假設其可以循環(huán)移
位，問循環(huán)左移多少位能夠得到最小的字符串。
算法即是周源的最小表示法，搜索可以找到相關論文和ppt。
該算法其實也不是太復雜，思路可以這樣理解。假設原字符串為s，設s1 = s + s; s2 = s1循
環(huán)左移1位;現(xiàn)在處理s1和s2，實際寫程序的時候可以通過下標偏移和取模得到s1和s2，而并不需
要生成。
處理過程是這樣的，設i和j分別指向s1和s2的開頭。我們的目的是找到這樣的i和j，假設k是s的
長度，滿足條件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有滿足條件的字符串中最小的
字符串，如果有多個這樣的s1[i,i+k-1] 那么我們希望i最小。
其實這個算法主要是做了一個優(yōu)化，從而把時間搞成線性的。比如，對于當前的i和j，我們一直
進行匹配，也就是s1[i,i+k] = s2[j,j+k] 一直滿足，突然到了一個位置s1[i+k] != s2[j+k]了，
現(xiàn)在我們需要改變i和j了。但是，我們不能只是++i或者++j。而是根據(jù)s1[i+k]>s2[j+k]的話i =
i + k + 1，否則j = j + k + 1。這樣的瞬移i或者j就能夠保證復雜度是線性的了。
問題是如何證明可以這樣的瞬移。其實，說穿了也很簡單。因為s1[i,i+k - 1] = s2[j,j+k -1]
是滿足的，只是到了s1[i+k]和s2[j+k]才出現(xiàn)問題了。假如s1[i+k]>s2[j+k]，那么我們改變i為
區(qū)間[i+1,i+k]中任何一個值m都不可能得到我們想要的答案，這是因為我們總可以在s2中找到相應
的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1]，因為有s1[i+k]>s2[j+k]。
同樣對于s1[i+k]<s2[j+k]的情況。
文字可能描述的不是很清楚。看PPT能夠根據(jù)圖進行分析。
代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <algorithm>
#include <
string>
#include <iostream>
using namespace std;
int GetMin(
string& str)
{
int nSize = str.size();
int i = 0, j = 1, k = 0;
while (i < nSize && j < nSize && k < nSize)
{
char chDif = str[(i + k) % nSize]
- str[(j + k) % nSize];
if (!chDif) ++k;
else {
if (chDif > 0) i = i + k + 1;
else j = j + k + 1;
if (i == j) ++j;
k = 0;
}
}
return min(i, j);
}
int main()
{
string str;
int nN;
scanf("%d", &nN);
while (nN--)
{
cin >> str;
printf("%d\n", GetMin(str) + 1);
}
return 0;
}