獲取相同字串所需的最小旋轉次數的 PHP 程式

---

在這個問題中，我們需要透過執行字串的旋轉來獲得相同的字串，並且需要計算旋轉次數。

解決這個問題可能有不同的方法，但在這裡我們將學習一些 PHP 中的最佳方法。第一種方法使用旋轉子字串，另一種方法從特定索引將字串分成兩部分。

問題陳述 - 我們有一個包含 n 個字元的字串 str。我們必須找到我們應該執行的字串的最小旋轉次數才能再次獲得相同的字串。

示例

輸入

str = "bcbc";

輸出

2

說明 - 在第一次旋轉中，字串變為 'cbcb'，在第二次旋轉中，字串變為 'bcbc'。因此，我們需要總共 2 次旋轉才能再次獲得原始字串。

輸入

 str = "opqropqr"

輸出

4

說明 - 當我們執行 4 次左旋轉時，我們可以獲得原始字串。

輸入

 str = ‘lnm’

輸出

3

說明 - 該字串不包含任何重複的字串。因此，我們需要執行等於字串長度的總旋轉次數。

方法 1

在這種方法中，我們從每個索引獲取長度等於 str 字串長度的子字串，並檢查它是否等於 str 字串。如果是，則問題的答案是 p。

演算法

步驟 1 - 使用“.” 運算子將 str 字串與其自身組合。

步驟 2 - 從索引 1 開始進行總共“len”次迭代。

步驟 3 - 使用 substr() 方法並傳遞引數。它將字串作為第一個引數，起始索引作為第二個引數，子字串的長度作為第三個引數。

步驟 4 - 如果 str 和結果字串相等，則返回當前索引值。

步驟 5 - 如果我們找不到字串旋轉，則最後返回“len”。

示例

<?php
function totalRotations($str){
    // Merge the string
    $tmp = ($str . $str);
    $len = strlen($str);
    // iterate the string
    for ($p = 1; $p <= $len; $p++) {
        // get a substring
        $substring = substr($tmp, $p, $len);
        // return $i, if the substring matches with the original string
        if ($str == $substring)
            return $p;
    }
    return $len;
}
$str = "bcbc";
echo "The total numbers of rotations required to get the original string are: ";
echo totalRotations($str), "\n";
?>

輸出

The total numbers of rotations required to get the original string are: 2

時間複雜度 - O(N^2) 以在迴圈內找到子字串。

空間複雜度 - O(N) 以儲存子字串。

我們學習瞭如何找到獲取相同字串所需的最小旋轉次數。此外，使用者可以解決我們需要找到獲取原始字串所需的總右旋轉次數的問題，以進行更多練習。