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!