C++ N长度的字符串中包含S作为子序列的数量

给定一个长度为S的字符串，再给定一个数字n，表示可能包含S作为子序列的字符串的长度。我们需要找到长度为N的唯一字符串的数量，其中包含S作为子序列，其中子序列是从给定字符串中取出的字符集合，可以是所有字符也可以不是，并且它们不需要连续。

示例

输入1

string str = "xyz"
int n = 3

输出

1

解释

只有一个长度为3的字符串包含给定的字符串作为其子序列。

输入2

string str = "aback"
int n = 4

输出

0

解释

长度为4的字符串无法存储大小为5的子序列，或者给定字符串的长度超过了给定的字符串，因此没有解决方案。

输入3

string str = "aba"
int n = 5

结果

6376

方法

我们已经看到了上面的例子以了解这个问题。在这种方法中，我们将使用排列和组合的概念。

我们将创建一个函数，该函数将以当前字符串和给定的数N作为输入，并返回表示所需字符串数量的整数。

在函数中，我们将创建一个数组，该数组将存储从数字0到数字N的阶乘结果。

我们将使用for循环遍历给定字符串的长度和给定的数N之间的范围。

要获取组合数nCr的值，我们需要定义另一个函数，该函数将以n、r和阶乘作为输入，并返回所需的值。

我们将定义另一个函数getPower，该函数将返回给定数字对给定值的幂，但是要注意它将返回带有模运算的值。

我们将调用nCr函数，然后从那里调用power函数并获取代码中可以看到的所需方法。

示例

#include <bits/stdc++.h>
using namespace std;

int mod = 1e9 + 7; // mod value to take mod with 
// function to get the power as the function of mod
long long getPower(long long num1, long long num2){
   long long ans = 1;
   num1 = num1 % mod;
   if(num1 == 0){
      return 0;
   }
   while(num2 > 0){
      if(num2 & 1){
         ans = (ans * num1) % mod;
      }
      num2 /= 2;
      num1 = (num1 * num1) % mod;
   }
   return ans;
}
// get the value of the nCr
long long nCr(int n, int r, long long fact[]){
   // base case 
   if(r > n){
      return 0;
   }
   long long res = fact[n];
   res *= getPower(fact[r], mod - 2);
   res = res % mod; 
   res *= getPower(fact[n - r], mod - 2);
   res = res % mod;
   return res;
}
// function to get the required number of 
int numberOfStrings(string str, int n){
   int len = str.length(); // get the lenght of the given string 
   // if the n is less than than given stirng size
   // then there will be no string present of given length
   if(len > n){
      return 0;
   }
   // array to store the value of the factorials 
   long long fact[n + 1];
   fact[0] = 1; // initializing 0th index value 
   // calculating the result for the other indexes  
   for(int i = 1; i <= n; i++){
      fact[i] = fact[i - 1] * i;
      fact[i] %= mod;
   }
   // variable to store the result 
   long long res = 0;
   // iterating over the all the possible positions
   for (int i = len; i <= n; i++){
      long long temp = nCr(i-1, len-1, fact);
      temp *= getPower(26, n - i);
      temp %= mod;
      temp *= getPower(25, i - len);
      temp %= mod;
      res += temp;
      res %= mod;
   }
   return res;
}
int main(){
   int n = 5;
   string str = "aba";
   cout << "The number of strings of n length having str as a Subsequence are: "<< numberOfStrings(str, n)<<endl;
   return 0;
}

输出

The number of strings of n length having str as a Subsequence are: 6376

时间和空间复杂度

以上代码的时间复杂度是O(N*log(N))，其中N是给定的字符序列的限制。

以上代码的空间复杂度为O(N)，因为我们使用一个数组来存储长度为N的阶乘。

结论

在本教程中，我们实现了一个程序，用于计算包含给定字符串S作为子序列的给定长度N的字符串数量，并且字符串数量可能很大，因此我们需要对1e9 + 7取模。我们使用了阶乘和组合方法，以及与模运算相关的幂运算的方法。