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 = "Beginner" Output : 5 Input : s = "aaaa" Output : 1
The idea is based on below post. A Program to check if strings are rotations of each other or not 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.
PHP
<?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 = $tmp . substr ( $i , strlen ( $str )); // 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 ), " "; // This code is contributed // by Sachin ?> |
Output:
3
Time Complexity: O(n2) Please refer complete article on Minimum rotations required to get the same string for more details!
Auxiliary Space: O(n), The extra space is used to store the copied string in tmp variable.