算法研究之左旋字元串

今天看了一個大牛在網上寫的關于算法的研究，感觸頗深，是以寫下跟随其腳步研究的過程。

定義：定義字元串的左旋轉操作：把字元串前面的若幹個字元移動到字元串的尾部。 如把字元串abcdef左旋轉2位得到字元串cdefab。長度為7的數組，左旋2位即右移4位。

讓我們首先來看一個算法：先不考慮字元串的左旋，而是考慮一個字元數組的左旋——設計一個算法，把一個含有N個元素的數組循環右移K位，要求時間複雜度為O（N）， 且隻允許使用兩個附加變量。

對于這個問題：

解法1：可以每次将數組中的元素右移一位，循環K次。

結果為：

此算法複雜度為O(kxN)

解法2：

其實我們如果考慮到K如果大于N，即循環左旋，這樣我們可以看到右移K位之後的情形，跟右移K’= K % N位之後的情形一樣，是以我們可以改進這個算法

加入 K %= N  這樣一來，複雜度就變為O(n2)與k無關了。

解法3：

實際上從整體上來看，這個左旋的過程分為兩部分：

1、将數組分為兩部分，即要左旋的k位和剩下的數組。

2、将這兩部分交換下。

變換的步驟執行個體如下：

逆序排列abcd：abcd1234 → dcba1234； 

逆序排列1234：dcba1234 → dcba4321； 

全部逆序：dcba4321 → 1234abcd。

實作如下：

輸出結果相同。

而這樣使用三次翻轉的算法，将時間複雜度控制到了線性。

現在我們回到原題上來，對字元串的左旋，現在看來就比較簡單了

拿abcdef 這個例子來說：

1、首先分為倆部分，X:abc，Y:def； 

2、X->X^T，abc->cba， Y->Y^T，def->fed。 

3、(X^TY^T)^T=YX，cbafed->defabc，即整個翻轉。

以上。