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

---

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

示例

输入

string str = "xyz"
int n = 3

输出

1

解释

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

输入

string str = "aback"
int n = 4

输出

0

解释

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

输入

string str = "aba"
int n = 5

输出

6376

方法

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

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

在函数中，我们将创建一个数组，用于存储从 0 到 N（包括 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 的阶乘。

结论

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