text: Count number of ways to convert string S to T by performing K cyclic shifts | C ++ program for the above approach ; Function to count number of ways to convert string S to string T by performing K cyclic shifts ; Calculate length of string ; ' a ' is no of good cyclic shifts ' b ' is no of bad cyclic shifts ; Iterate in the string ; Precompute the number of good and bad cyclic shifts ; dp2 [ i ] to store the no of ways to get to a bad shift in i moves ; Calculate good and bad shifts ; Return the required number of ways ; Driver Code ; Given Strings ; Given K shifts required ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define mod  10000000007 NEW_LINE long long countWays ( string s , string t , int k ) { int n = s . size ( ) ; int a = 0 , b = 0 ; for ( int i = 0 ; i < n ; i ++ ) { string p = s . substr ( i , n - i ) + s . substr ( 0 , i ) ; if ( p == t ) a ++ ; else b ++ ; } vector < long long > dp1 ( k + 1 ) , dp2 ( k + 1 ) ; if ( s == t ) { dp1 [ 0 ] = 1 ; dp2 [ 0 ] = 0 ; } else { dp1 [ 0 ] = 0 ; dp2 [ 0 ] = 1 ; } for ( int i = 1 ; i <= k ; i ++ ) { dp1 [ i ] = ( ( dp1 [ i - 1 ] * ( a - 1 ) ) % mod + ( dp2 [ i - 1 ] * a ) % mod ) % mod ; dp2 [ i ] = ( ( dp1 [ i - 1 ] * ( b ) ) % mod + ( dp2 [ i - 1 ] * ( b - 1 ) ) % mod ) % mod ; } return dp1 [ k ] ; } int main ( ) { string S = " ab " , T = " ab " ; int K = 2 ; cout << countWays ( S , T , K ) ; return 0 ; }