看到两道今日头条的面试题[1]，尝试做了下，在这里整理下思路。
String Shifting
naive 的方法不用说了，时间复杂度 O(n^2)，肯定不是面试官想要的答案了。
假设 shift k 次的时候发生了第一次 match，那么再 shift k 次必然再次 match，并且小于 k 时不可能 match。所以可知该字符串 S 是以 S[0:k] 为周期重复的。所以问题转变成求字符串的最小周期。用 KMP 的 partial match table 可求[2]，时间复杂度 O(n)。
字典序
这是个排序问题。首先要明白什么是字典序，字典序和自然数序列不同，不是可以直接生成的，而是通过比较两个字符串的大小排序生成的。对于 Java 而言，就是实现一个 comparator 然后 sort 就可以了，时间复杂度 O(nlgn)，数据量太大的话可以 divide，然后 merge sort。
再进一步想其实这个问题很像 Kth Largest Element in an Array 问题[3]，用 heap，时间复杂度 O(klgn)[4]。
