Подсчитайте количество способов преобразовать строку S в T, выполнив K циклических сдвигов

Опубликовано: 5 Января, 2022

Учитывая две строки 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:
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:
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, и наоборот для «плохого» . Ниже приведены шаги:

  1. Предварительно вычислите количество хороших (обозначено a) и плохих (обозначено b) циклических сдвигов.
  2. Инициализируйте два массива dp таким образом, чтобы dp1 [i] обозначало количество способов получить хороший сдвиг за i ходов, а dp2 [i] обозначало количество способов добраться до плохого сдвига за i ходов .
  3. Для перехода нас интересует только предыдущее состояние, т.е. (i - 1) -е состояние, и ответ на этот вопрос - dp1 [K] .
  4. Таким образом, количество способов достичь хорошего состояния за i ходов равно количеству способов достижения хорошего сдвига за i-1 ходов, умноженному на (a-1) (поскольку последний сдвиг также хорош)
  5. Таким образом, количество способов достижения плохого сдвига в 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.