赤裸裸的字符串最小表示題。所謂字符串最小表示指的是給定一個(gè)字符串，假設(shè)其可以循環(huán)移
位，問(wèn)循環(huán)左移多少位能夠得到最小的字符串。
算法即是周源的最小表示法，搜索可以找到相關(guān)論文和ppt。
該算法其實(shí)也不是太復(fù)雜，思路可以這樣理解。假設(shè)原字符串為s，設(shè)s1 = s + s; s2 = s1循
環(huán)左移1位;現(xiàn)在處理s1和s2，實(shí)際寫(xiě)程序的時(shí)候可以通過(guò)下標(biāo)偏移和取模得到s1和s2，而并不需
要生成。
處理過(guò)程是這樣的，設(shè)i和j分別指向s1和s2的開(kāi)頭。我們的目的是找到這樣的i和j，假設(shè)k是s的
長(zhǎng)度，滿足條件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有滿足條件的字符串中最小的
字符串，如果有多個(gè)這樣的s1[i,i+k-1] 那么我們希望i最小。
其實(shí)這個(gè)算法主要是做了一個(gè)優(yōu)化，從而把時(shí)間搞成線性的。比如，對(duì)于當(dāng)前的i和j，我們一直
進(jìn)行匹配，也就是s1[i,i+k] = s2[j,j+k] 一直滿足，突然到了一個(gè)位置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就能夠保證復(fù)雜度是線性的了。
問(wèn)題是如何證明可以這樣的瞬移。其實(shí)，說(shuō)穿了也很簡(jiǎn)單。因?yàn)閟1[i,i+k - 1] = s2[j,j+k -1]
是滿足的，只是到了s1[i+k]和s2[j+k]才出現(xiàn)問(wèn)題了。假如s1[i+k]>s2[j+k]，那么我們改變i為
區(qū)間[i+1,i+k]中任何一個(gè)值m都不可能得到我們想要的答案，這是因?yàn)槲覀兛偪梢栽趕2中找到相應(yīng)
的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1]，因?yàn)橛衧1[i+k]>s2[j+k]。
同樣對(duì)于s1[i+k]<s2[j+k]的情況。
文字可能描述的不是很清楚。看PPT能夠根據(jù)圖進(jìn)行分析。
代碼如下：
#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;
}