長度為 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 取模。我們使用階乘和組合方法以及模冪的方法實現了一種方法。