PHP Program for Minimum rotations required to get the same string

Given a string, we need to find the minimum number of rotations required to get the same string.

Examples:

Input : s = "geeks"
Output : 5

Input : s = "aaaa"
Output : 1

Algorithm:

• Step 1: Initialize result = 0 (Here result is count of rotations)
• Step 2: Take a temporary string equals to original string concatenated with itself.
• Step 3: Now take the substring of temporary string of size same as original string starting from second character (or index 1).
• Step 4: Increase the count.
• Step 5: Check whether the substring becomes equal to original string. If yes, then break the loop. Else go to step 2 and repeat it from the next index. 

Below is the implementation of the above algorithm:

<?php
// PHP program to determine minimum 
// number of rotations required to 
// yield same string. 

// Returns count of rotations 
// to get the same string back. 
function findRotations($str) 
{ 
    // tmp is the concatenated string. 
    $tmp = $str . $str; 
    $n = strlen($str); 

    for ($i = 1; $i <= $n; $i++)
    { 
        // substring from i index 
        // of original string size. 
        $substring = substr($tmp, $i, $n); 

        // if substring matches with 
        // original string then we will 
        // come out of the loop. 
        if ($str == $substring) 
            return $i; 
    } 
    return $n; 
} 

// Driver code 
$str = "abc"; 
echo findRotations($str), "\n"; 

// This code is contributed 
// by Sachin
?>

3

Complexity Analysis:

• Time Complexity: O(n²)
• Auxiliary Space: O(n), The extra space is used to store the copied string in tmp variable.

Please refer complete article on Minimum rotations required to get the same string for more details!