程式設計之美之字元串移位包含問題

給定兩個字元串s1和s2，要求判斷s2是否能夠被通過s1做循環移位（rotate）得到的字元串包含。例如，S1=AABCD和s2=CDAA，傳回true；給定s1=ABCD和s2=ACBD，傳回false。

【思路一】

從題目中可以看出，我們可以使用最直接的方法對S1進行循環移動，再進行字元串包含的判斷，進而周遊其所有的可能性。

字元串循環移動，時間複雜度為O（n），字元串包含判斷，采用普通的方法，時間複雜度為O（n*m），總體複雜度為O（n*n*m）。

字元串包含判斷，若采用KMP算法，時間複雜度為O（n），這樣總體的複雜度為O（n*n）。若字元串的長度n較大，顯然效率比較低。其中n為S1的長度，m為S2的長度。

【思路二】

我們也可以對循環移位之後的結果進行分析。

以S1 = ABCD為例，先分析對S1進行循環移位之後的結果，如下所示：

ABCD--->BCDA---->CDAB---->DABC---->ABCD……

假設我們把前面的移走的資料進行保留，會發現有如下的規律：

ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……

是以，可以看出對S1做循環移位所得到的字元串都将是字元串S1S1的子字元串。如果S2可以由S1循環移位得到，那麼S2一定在S1S1上，這樣時間複雜度就降低了。