Подсчитайте количество способов преобразовать строку S в T, выполнив K циклических сдвигов
Учитывая две строки S и T и число K , задача состоит в том, чтобы подсчитать количество способов преобразовать строку S в строку T путем выполнения K циклических сдвигов .
The cyclic shift is defined as the string S can be split into two non-empty parts X + Y and in one operation we can transform S to Y + X from X + Y.
Примечание: так как count может быть очень большим, выведите ответ по модулю 10 9 + 7 .
Примеры:
Input: S = “ab”, T = “ab”, K = 2
Output: 1
Explanation:
The only way to do this is to convert [ab to ba] in the first move and then [ba to ab] in the second move.
Input: S = “ababab”, T = “ababab”, K = 1
Output: 2
Explanation:
One possible way to convert S to T in one move is [ab | abab] -> [ababab], the second way is [abab | ab] -> [ababab]. So there are total two ways.
Подход: эту проблему можно решить с помощью динамического программирования. Назовем циклический сдвиг «хорошим», если в конце мы находимся в строке T, и наоборот для «плохого» . Ниже приведены шаги:
- Предварительно вычислите количество хороших (обозначено a) и плохих (обозначено b) циклических сдвигов.
- Инициализируйте два массива dp таким образом, чтобы dp1 [i] обозначало количество способов получить хороший сдвиг за i ходов, а dp2 [i] обозначало количество способов добраться до плохого сдвига за i ходов .
- Для перехода нас интересует только предыдущее состояние, т.е. (i - 1) -е состояние, и ответ на этот вопрос - dp1 [K] .
- Таким образом, количество способов достичь хорошего состояния за i ходов равно количеству способов достижения хорошего сдвига за i-1 ходов, умноженному на (a-1) (поскольку последний сдвиг также хорош)
- Таким образом, количество способов достижения плохого сдвига в i-1 ходах умножается на (а) (поскольку следующим ходом может быть любой из хороших сдвигов).
Ниже приведено соотношение повторяемости для хороших и плохих сдвигов:
So for good shifts we have:
Similarly, for bad shifts we have:
Ниже представлена реализация вышеуказанного подхода:
C ++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define mod 10000000007 // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts long long countWays(string s, string t, int k) { // Calculate length of string int n = s.size(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for ( int i = 0; i < n; i++) { string p = s.substr(i, n - i) + s.substr(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves 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; } // Calculate good and bad shifts 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 the required number of ways return dp1[k]; } // Driver Code int main() { // Given Strings string S = "ab" , T = "ab" ; // Given K shifts required int K = 2; // Function Call cout << countWays(S, T, K); return 0; } |
Джава
// Java program for above approach class GFG{ static long mod = 10000000007L; // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts static long countWays(String s, String t, int k) { // Calculate length of string int n = s.length(); // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0 , b = 0 ; // Iterate in the string for ( int i = 0 ; i < n; i++) { String p = s.substring(i, n - i) + s.substring( 0 , i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves long dp1[] = new long [k + 1 ]; long dp2[] = new long [k + 1 ]; if (s == t) { dp1[ 0 ] = 1 ; dp2[ 0 ] = 0 ; } else { dp1[ 0 ] = 0 ; dp2[ 0 ] = 1 ; } // Calculate good and bad shifts 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 the required number of ways return dp1[k]; } // Driver code public static void main(String[] args) { // Given Strings String S = "ab" , T = "ab" ; // Given K shifts required int K = 2 ; // Function Call System.out.print(countWays(S, T, K)); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach mod = 1000000007 # Function to count number of ways # to convert string S to string T by # performing K cyclic shifts def countWays(s, t, k): # Calculate length of string n = len (s) # a is no. of good cyclic shifts # b is no. of bad cyclic shifts a = 0 b = 0 # Iterate in string for i in range (n): p = s[i : n - i + 1 ] + s[: i + 1 ] # Precompute the number of good # and bad cyclic shifts if (p = = t): a + = 1 else : b + = 1 # Initialize two dp arrays # dp1[i] to store the no of ways to # get to a goof shift in i moves # dp2[i] to store the no of ways to # get to a bad shift in i moves dp1 = [ 0 ] * (k + 1 ) dp2 = [ 0 ] * (k + 1 ) if (s = = t): dp1[ 0 ] = 1 dp2[ 0 ] = 0 else : dp1[ 0 ] = 0 dp2[ 0 ] = 1 # Calculate good and bad shifts for i in range ( 1 , k + 1 ): 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 the required number of ways return (dp1[k]) # Driver Code # Given Strings S = 'ab' T = 'ab' # Given K shifts required K = 2 # Function call print (countWays(S, T, K)) # This code is contributed by Arjun Saini |
C #
// C# program for the above approach using System; class GFG{ static long mod = 10000000007L; // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts static long countWays( string s, string t, int k) { // Calculate length of string int n = s.Length; // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts int a = 0, b = 0; // Iterate in the string for ( int i = 0; i < n; i++) { string p = s.Substring(i, n - i) + s.Substring(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves long []dp1 = new long [k + 1]; long []dp2 = new long [k + 1]; if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts 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 the required number of ways return dp1[k]; } // Driver code public static void Main( string [] args) { // Given Strings string S = "ab" , T = "ab" ; // Given K shifts required int K = 2; // Function call Console.Write(countWays(S, T, K)); } } // This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript program for the above approach let mod = 10000000007; // Function to count number of ways to // convert string S to string T by // performing K cyclic shifts function countWays(s, t, k) { // Calculate length of string let n = s.length; // 'a' is no of good cyclic shifts // 'b' is no of bad cyclic shifts let a = 0, b = 0; // Iterate in the string for (let i = 0; i < n; i++) { let p = s.substr(i, n - i) + s.substr(0, i); // Precompute the number of good // and bad cyclic shifts if (p == t) a++; else b++; } // Initialize two dp arrays // dp1[i] to store the no of ways to // get to a good shift in i moves // dp2[i] to store the no of ways to // get to a bad shift in i moves let dp1 = Array.from({length: k+1}, (_, i) => 0); let dp2 = Array.from({length: k+1}, (_, i) => 0); if (s == t) { dp1[0] = 1; dp2[0] = 0; } else { dp1[0] = 0; dp2[0] = 1; } // Calculate good and bad shifts for (let 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 the required number of ways return dp1[k]; } // Driver Code // Given Strings let S = "ab" , T = "ab" ; // Given K shifts required let K = 2; // Function Call document.write(countWays(S, T, K)); </script> |
1
Сложность времени: O (N)
Вспомогательное пространство: O (K)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.