String Problem
Problem Description
Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings: String Rank SKYLONG 1 KYLONGS 2 YLONGSK 3 LONGSKY 4 ONGSKYL 5 NGSKYLO 6 GSKYLON 7 and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once. Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Input
Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.
Output
Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Sample Input
abcder aaaaaa ababab
Sample Output
1 1 6 1 1 6 1 6 1 3 2 3
Author
WhereIsHeroFrom
Source
HDOJ Monthly Contest – 2010.04.04
循環字元串的最小表示法的問題可以這樣描述：
對于一個字元串S，求S的循環的同構字元串S’中字典序最小的一個。
由于語言能力有限，還是用實際例子來解釋比較容易： 設S=bcad，且S’是S的循環同構的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。 對于字元串循環同構的最小表示法，其問題實質是求S串的一個位置，從這個位置開始循環輸出S，得到的S’字典序最小。 一種樸素的方法是設計i,j兩個指針。其中i指向最小表示的位置，j作為比較指針。
令i=0,j=1 如果S[i] > S[j] i=j, j=i+1 如果S[i] < S[j] j++ 如果S[i]==S[j] 設指針k，分别從i和j位置向下比較，直到S[i] != S[j] 如果S[i+k] > S[j+k] i=j,j=i+1 否則j++ 傳回i
起初，我想在j指針後移的過程中加入一個優化。就是j每次不是加1，而是移動到l位置。其中，l>j且S[l]<=S[j]。但是，即使加入這一優化，在遇到bbb…bbbbbba這樣的字元串時複雜度将退化到O(n^2)。
注意到，樸素算法的缺陷在于斜體的情況下i指針的移動太少了。針對這一問題改進就得到了最小表示法的算法。最小表示法的算法思路是維護兩個指針i,j。
令i=0,j=1 如果S[i] > S[j] i=j, j=i+1 如果S[i] < S[j] j++ 如果S[i]==S[j] 設指針k，分别從i和j位置向下比較，直到S[i] != S[j] 如果S[i+k] > S[j+k] i=i+k 否則j++ 傳回i和j的小者
注意到上面兩個算法唯一的差別是粗體的一行。這一行就把複雜度降到O(n)了。 值得一提的是，與KMP類似，最小表示法處理的是一個字元串S的性質，而不是看論文時給人感覺的處理兩個字元串。 應用最小表示法判斷兩個字元串同構，隻要将兩個串的最小表示求出來，然後從最小表示開始比較。剩下的工作就不用多說了。
[cpp] view plaincopy
int MinimumRepresentation(char *s, int l)
{
int i = 0, j = 1, k = 0, t;
while(i < l && j < l && k < l) {
t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];
if(!t) k++;
else{
if(t > 0) i = i + k + 1;
else j = j + k + 1;
if(i == j) ++ j;
k = 0;
}
}
return (i < j ? i : j);
}