看到兩道今日頭條的面試題^[1]，嘗試做了下，在這里整理下思路。

String Shifting

naive 的方法不用說了，時間復(fù)雜度 O(n^2)，肯定不是面試官想要的答案了。

假設(shè) shift k 次的時候發(fā)生了第一次 match，那么再 shift k 次必然再次 match，并且小于 k 時不可能 match。所以可知該字符串 S 是以 S[0:k] 為周期重復(fù)的。所以問題轉(zhuǎn)變成求字符串的最小周期。用 KMP 的 partial match table 可求^[2]，時間復(fù)雜度 O(n)。

字典序

這是個排序問題。首先要明白什么是字典序，字典序和自然數(shù)序列不同，不是可以直接生成的，而是通過比較兩個字符串的大小排序生成的。對于 Java 而言，就是實現(xiàn)一個 comparator 然后 sort 就可以了，時間復(fù)雜度 O(nlgn)，數(shù)據(jù)量太大的話可以 divide，然后 merge sort。

再進(jìn)一步想其實這個問題很像 Kth Largest Element in an Array 問題^[3]，用 heap，時間復(fù)雜度 O(klgn)^[4]。

1. http://li5jun.com/article/89.html ?

2. http://stackoverflow.com/a/33864413/1872897 ?

3. https://leetcode.com/problems/kth-largest-element-in-an-array/ ?

4. http://www.programcreek.com/2014/05/leetcode-kth-largest-element-in-an-array-java/ ?