获取相同字符串所需的最小旋转次数的 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) 以存储子字符串。

我们学习了如何找到获取相同字符串所需的最小旋转次数。此外，用户可以解决我们需要找到获取原始字符串所需的总右旋转次数的问题，以进行更多练习。