将不同的事件作为子序列进行计数-yiteyi-C++库

给定两个字符串S和T，求T在S中作为子序列出现的次数。 例如：

null

Input: S = banana, T = banOutput: 3Explanation: T appears in S as below three subsequences.[ban], [ba  n], [b   an]Input: S = geeksforgeeks, T = geOutput: 6Explanation: T appears in S as below three subsequences.[ge], [     ge], [g e], [g    e] [g     e]and [     g e]

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 创建一个递归函数，使其返回 s 那场比赛 T 这里m是T的长度，n是S的长度。这个问题可以递归地定义如下。

考虑到绳子 T 是空字符串，返回1作为空字符串可以是所有字符串的子序列。
考虑到绳子 s 是空字符串，返回0，因为任何字符串都不能是空字符串的子序列。
如果 s 和 T 不匹配，然后删除的最后一个字符 s 然后再次调用递归函数。因为S的最后一个字符不能是子序列的一部分，也不能删除它并检查其他字符。
如果 s 匹配然后可以有两种可能性，首先可以有一个子序列，其中 s 是它的一部分，第二个不是子序列的一部分。因此，所需的值将是两者的总和。在删除两个字符串的最后一个字符的情况下调用递归函数一次，在仅删除两个字符串的最后一个字符的情况下再次调用递归函数 s 远离的。

图片[1]-将不同的事件作为子序列进行计数-yiteyi-C++库

蓝色的圆形矩形代表可接受的状态或存在子序列，红色的圆形矩形代表无法形成子序列。 由于上述递推结果中存在重叠子问题，可以采用动态规划方法来解决上述问题。将子问题存储在哈希映射或数组，并在再次调用函数时返回值。 算法：

创建二维阵列 材料[m+1][n+1] 其中m是字符串T的长度，n是字符串S的长度。mat[i][j]表示子字符串S（1..i）和子字符串T（1..j）的不同子序列的数量，因此mat[m][n]包含我们的解。
用所有0初始化第一列。空字符串不能有另一个字符串作为子序列
用所有1初始化第一行。空字符串是所有字符串的子序列。
以自下而上的方式填充矩阵，即首先计算当前字符串的所有子问题。
穿过绳子 T 从头到尾。（柜台是我 )
对于外部循环的每次迭代，遍历字符串 s 从头到尾。（柜台是 J )
如果角色我字符串的第四个索引 T 匹配 J 字符串的第个字符 s 考虑到两种情况，得出了该值。首先，是S中没有最后一个字符的所有子字符串，第二个是两者中都没有最后一个字符的子字符串，即 mat[i+1][j]+mat[i][j] .
否则，即使 J 第四个字符 s 被移除，即垫[i+1][j]
打印 材料[m-1][n-1] 作为答案。

C++

                         /* C/C++ program to count number of times S appears                       
                                                 as a subsequence in T */                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     findSubsequenceCount(string S, string T)                       
                         {                       
                                                 int                                     m = T.length(), n = S.length();                       
           
                                                 // T can't appear as a subsequence in S                       
                                                 if                                     (m > n)                       
                                                 return                                     0;                       
           
                                                 // mat[i][j] stores the count of occurrences of                       
                                                 // T(1..i) in S(1..j).                       
                                                 int                                     mat[m + 1][n + 1];                       
           
                                                 // Initializing first column with all 0s. An empty                       
                                                 // string can't have another string as subsequence                       
                                                 for                                     (                                     int                                     i = 1; i <= m; i++)                       
                                                 mat[i][0] = 0;                       
           
                                                 // Initializing first row with all 1s. An empty                       
                                                 // string is subsequence of all.                       
                                                 for                                     (                                     int                                     j = 0; j <= n; j++)                       
                                                 mat[0][j] = 1;                       
           
                                                 // Fill mat[][] in bottom up manner                       
                                                 for                                     (                                     int                                     i = 1; i <= m; i++) {                       
                                                 for                                     (                                     int                                     j = 1; j <= n; j++) {                       
           
                                                 // If last characters don't match, then value                       
                                                 // is same as the value without last character                       
                                                 // in S.                       
                                                 if                                     (T[i - 1] != S[j - 1])                       
                                                 mat[i][j] = mat[i][j - 1];                       
           
                                                 // Else value is obtained considering two cases.                       
                                                 // a) All substrings without last character in S                       
                                                 // b) All substrings without last characters in                       
                                                 // both.                       
                                                 else                       
                                                 mat[i][j] = mat[i][j - 1] + mat[i - 1][j - 1];                       
                                                 }                       
                                                 }                       
           
                                                 /* uncomment this to print matrix mat                       
                                                 for (int i = 1; i <= m; i++, cout << endl)                       
                                                 for (int j = 1; j <= n; j++)                       
                                                 cout << mat[i][j] << " ";  */                       
                                                 return                                     mat[m][n];                       
                         }                       
           
                         // Driver code to check above method                       
                         int                                     main()                       
                         {                       
                                                 string T =                                     "ge"                                     ;                       
                                                 string S =                                     "geeksforgeeks"                                     ;                       
                                                 cout << findSubsequenceCount(S, T) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number of times                       
                         // S appears as a subsequence in T                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                                 static                                     int                                     findSubsequenceCount(String S, String T)                       
                                                 {                       
                                                 int                                     m = T.length();                       
                                                 int                                     n = S.length();                       
           
                                                 // T can't appear as a subsequence in S                       
                                                 if                                     (m > n)                       
                                                 return                                     0                                     ;                       
           
                                                 // mat[i][j] stores the count of                       
                                                 // occurrences of T(1..i) in S(1..j).                       
                                                 int                                     mat[][] =                                     new                                     int                                     [m +                                     1                                     ][n +                                     1                                     ];                       
           
                                                 // Initializing first column with                       
                                                 // all 0s. An emptystring can't have                       
                                                 // another string as subsequence                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= m; i++)                       
                                                 mat[i][                                     0                                     ] =                                     0                                     ;                       
           
                                                 // Initializing first row with all 1s.                       
                                                 // An empty string is subsequence of all.                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <= n; j++)                       
                                                 mat[                                     0                                     ][j] =                                     1                                     ;                       
           
                                                 // Fill mat[][] in bottom up manner                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= m; i++) {                       
                                                 for                                     (                                     int                                     j =                                     1                                     ; j <= n; j++) {                       
                                                 // If last characters don't match,                       
                                                 // then value is same as the value                       
                                                 // without last character in S.                       
                                                 if                                     (T.charAt(i -                                     1                                     ) != S.charAt(j -                                     1                                     ))                       
                                                 mat[i][j] = mat[i][j -                                     1                                     ];                       
           
                                                 // Else value is obtained considering two cases.                       
                                                 // a) All substrings without last character in S                       
                                                 // b) All substrings without last characters in                       
                                                 // both.                       
                                                 else                       
                                                 mat[i][j] = mat[i][j -                                     1                                     ] + mat[i -                                     1                                     ][j -                                     1                                     ];                       
                                                 }                       
                                                 }                       
           
                                                 /* uncomment this to print matrix mat                       
                                                 for (int i = 1; i <= m; i++, cout << endl)                       
                                                 for (int j = 1; j <= n; j++)                       
                                                 System.out.println ( mat[i][j] +" "); */                       
                                                 return                                     mat[m][n];                       
                                                 }                       
           
                                                 // Driver code to check above method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String T =                                     "ge"                                     ;                       
                                                 String S =                                     "geeksforgeeks"                                     ;                       
                                                 System.out.println(findSubsequenceCount(S, T));                       
                                                 }                       
                         }                       
                         // This code is contributed by vt_m                       

Python3

                         # Python3 program to count number of times                       
                         # S appears as a subsequence in T                       
                         def                                     findSubsequenceCount(S, T):                       
           
                                                 m                                     =                                     len                                     (T)                       
                                                 n                                     =                                     len                                     (S)                       
           
                                                 # T can't appear as a subsequence in S                       
                                                 if                                     m > n:                       
                                                 return                                     0                       
           
                                                 # mat[i][j] stores the count of                       
                                                 # occurrences of T(1..i) in S(1..j).                       
                                                 mat                                     =                                     [[                                     0                                     for                                     _                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     __                                     in                                     range                                     (m                                     +                                     1                                     )]                       
           
                                                 # Initializing first column with all 0s. x                       
                                                 # An empty string can't have another                       
                                                 # string as subsequence                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , m                                     +                                     1                                     ):                       
                                                 mat[i][                                     0                                     ]                                     =                                     0                       
           
                                                 # Initializing first row with all 1s.                       
                                                 # An empty string is subsequence of all.                       
                                                 for                                     j                                     in                                     range                                     (n                                     +                                     1                                     ):                       
                                                 mat[                                     0                                     ][j]                                     =                                     1                       
           
                                                 # Fill mat[][] in bottom up manner                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , m                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
           
                                                 # If last characters don't match,                       
                                                 # then value is same as the value                       
                                                 # without last character in S.                       
                                                 if                                     T[i                                     -                                     1                                     ] !                                     =                                     S[j                                     -                                     1                                     ]:                       
                                                 mat[i][j]                                     =                                     mat[i][j                                     -                                     1                                     ]                       
                                   
                                                 # Else value is obtained considering two cases.                       
                                                 # a) All substrings without last character in S                       
                                                 # b) All substrings without last characters in                       
                                                 # both.                       
                                                 else                                     :                       
                                                 mat[i][j]                                     =                                     (mat[i][j                                     -                                     1                                     ]                                     +                       
                                                 mat[i                                     -                                     1                                     ][j                                     -                                     1                                     ])                       
           
                                                 return                                     mat[m][n]                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 T                                     =                                     "ge"                       
                                                 S                                     =                                     "geeksforgeeks"                       
                                                 print                                     (findSubsequenceCount(S, T))                       
           
                         # This code is contributed                       
                         # by vibhu4agarwal                       

C#

                         // C# program to count number of times                       
                         // S appears as a subsequence in T                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     findSubsequenceCount(                                     string                                     S,                                     string                                     T)                       
                                                 {                       
                                                 int                                     m = T.Length;                       
                                                 int                                     n = S.Length;                       
           
                                                 // T can't appear as a subsequence in S                       
                                                 if                                     (m > n)                       
                                                 return                                     0;                       
           
                                                 // mat[i][j] stores the count of                       
                                                 // occurrences of T(1..i) in S(1..j).                       
                                                 int                                     [, ] mat =                                     new                                     int                                     [m + 1, n + 1];                       
           
                                                 // Initializing first column with                       
                                                 // all 0s. An emptystring can't have                       
                                                 // another string as subsequence                       
                                                 for                                     (                                     int                                     i = 1; i <= m; i++)                       
                                                 mat[i, 0] = 0;                       
           
                                                 // Initializing first row with all 1s.                       
                                                 // An empty string is subsequence of all.                       
                                                 for                                     (                                     int                                     j = 0; j <= n; j++)                       
                                                 mat[0, j] = 1;                       
           
                                                 // Fill mat[][] in bottom up manner                       
                                                 for                                     (                                     int                                     i = 1; i <= m; i++) {                       
           
                                                 for                                     (                                     int                                     j = 1; j <= n; j++) {                       
           
                                                 // If last characters don't match,                       
                                                 // then value is same as the value                       
                                                 // without last character in S.                       
                                                 if                                     (T[i - 1] != S[j - 1])                       
                                                 mat[i, j] = mat[i, j - 1];                       
           
                                                 // Else value is obtained considering two cases.                       
                                                 // a) All substrings without last character in S                       
                                                 // b) All substrings without last characters in                       
                                                 // both.                       
                                                 else                       
                                                 mat[i, j] = mat[i, j - 1] + mat[i - 1, j - 1];                       
                                                 }                       
                                                 }                       
           
                                                 /* uncomment this to print matrix mat                       
                                                 for (int i = 1; i <= m; i++, cout << endl)                       
                                                 for (int j = 1; j <= n; j++)                       
                                                 System.out.println ( mat[i][j] +" "); */                       
                                                 return                                     mat[m, n];                       
                                                 }                       
           
                                                 // Driver code to check above method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     T =                                     "ge"                                     ;                       
                                                 string                                     S =                                     "geeksforgeeks"                                     ;                       
                                                 Console.WriteLine(findSubsequenceCount(S, T));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m                       

PHP

                         <?php                       
                         // PHP program to count number of times                       
                         // S appears as a subsequence in T */                       
           
                         function                                     findSubsequenceCount(                                     $S                                     ,                                     $T                                     )                       
                         {                       
                                                 $m                                     =                                     strlen                                     (                                     $T                                     );                                     $n                                     =                                     strlen                                     (                                     $S                                     );                       
           
                                                 // T can't appear as a subsequence in S                       
                                                 if                                     (                                     $m                                     >                                     $n                                     )                       
                                                 return                                     0;                       
           
                                                 // mat[i][j] stores the count of                       
                                                 // occurrences of T(1..i) in S(1..j).                       
                                                 $mat                                     =                                     array                                     (                                     array                                     ());                       
           
                                                 // Initializing first column with all 0s.                       
                                                 // An empty string can't have another                       
                                                 // string as subsequence                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $m                                     ;                                     $i                                     ++)                       
                                                 $mat                                     [                                     $i                                     ][0] = 0;                       
           
                                                 // Initializing first row with all 1s.                       
                                                 // An empty string is subsequence of all.                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <=                                     $n                                     ;                                     $j                                     ++)                       
                                                 $mat                                     [0][                                     $j                                     ] = 1;                       
           
                                                 // Fill mat[][] in bottom up manner                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $m                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 for                                     (                                     $j                                     = 1;                                     $j                                     <=                                     $n                                     ;                                     $j                                     ++)                       
                                                 {                       
                                                 // If last characters don't match,                       
                                                 // then value is same as the value                       
                                                 // without last character in S.                       
                                                 if                                     (                                     $T                                     [                                     $i                                     - 1] !=                                     $S                                     [                                     $j                                     - 1])                       
                                                 $mat                                     [                                     $i                                     ][                                     $j                                     ] =                                     $mat                                     [                                     $i                                     ][                                     $j                                     - 1];                       
           
                                                 // Else value is obtained considering two cases.                       
                                                 // a) All substrings without last character in S                       
                                                 // b) All substrings without last characters in                       
                                                 // both.                       
                                                 else                       
                                                 $mat                                     [                                     $i                                     ][                                     $j                                     ] =                                     $mat                                     [                                     $i                                     ][                                     $j                                     - 1] +                       
                                                 $mat                                     [                                     $i                                     - 1][                                     $j                                     - 1];                       
                                                 }                       
                                                 }                       
           
                                                 /* uncomment this to print matrix mat                       
                                                 for (int i = 1; i <= m; i++, cout << endl)                       
                                                 for (int j = 1; j <= n; j++)                       
                                                 cout << mat[i][j] << " "; */                       
                                                 return                                     $mat                                     [                                     $m                                     ][                                     $n                                     ];                       
                         }                       
           
                         // Driver Code                       
                         $T                                     =                                     "ge"                                     ;                       
                         $S                                     =                                     "geeksforgeeks"                                     ;                       
                         echo                                     findSubsequenceCount(                                     $S                                     ,                                     $T                                     ) .                                     ""                                     ;                       
           
                         // This code is contributed                       
                         // by Akanksha Rai                       

Javascript

                         <script>                       
           
                                                 // JavaScript program to count number of times                       
                                                 // S appears as a subsequence in T                       
                                   
                                                 function                                     findSubsequenceCount(S, T)                       
                                                 {                       
                                                 let m = T.length;                       
                                                 let n = S.length;                       
                                   
                                                 // T can't appear as a subsequence in S                       
                                                 if                                     (m > n)                       
                                                 return                                     0;                       
                                   
                                                 // mat[i][j] stores the count of                       
                                                 // occurrences of T(1..i) in S(1..j).                       
                                                 let mat =                                     new                                     Array(m + 1);                       
                                                 for                                     (let i = 0; i <= m; i++)                       
                                                 {                       
                                                 mat[i] =                                     new                                     Array(n + 1);                       
                                                 for                                     (let j = 0; j <= n; j++)                       
                                                 {                       
                                                 mat[i][j] = 0;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Initializing first column with                       
                                                 // all 0s. An emptystring can't have                       
                                                 // another string as subsequence                       
                                                 for                                     (let i = 1; i <= m; i++)                       
                                                 mat[i][0] = 0;                       
                                   
                                                 // Initializing first row with all 1s.                       
                                                 // An empty string is subsequence of all.                       
                                                 for                                     (let j = 0; j <= n; j++)                       
                                                 mat[0][j] = 1;                       
                                   
                                                 // Fill mat[][] in bottom up manner                       
                                                 for                                     (let i = 1; i <= m; i++) {                       
                                                 for                                     (let j = 1; j <= n; j++) {                       
                                                 // If last characters don't match,                       
                                                 // then value is same as the value                       
                                                 // without last character in S.                       
                                                 if                                     (T[i - 1] != S[j - 1])                       
                                                 mat[i][j] = mat[i][j - 1];                       
                                   
                                                 // Else value is obtained                       
                                                 // considering two cases.                       
                                                 // a) All substrings without                       
                                                 // last character in S                       
                                                 // b) All substrings without                       
                                                 // last characters in                       
                                                 // both.                       
                                                 else                       
                                                 mat[i][j] = mat[i][j - 1] +                       
                                                 mat[i - 1][j - 1];                       
                                                 }                       
                                                 }                       
                                   
                                                 /* uncomment this to print matrix mat                       
                                                 for (int i = 1; i <= m; i++, cout << endl)                       
                                                 for (int j = 1; j <= n; j++)                       
                                                 System.out.println ( mat[i][j] +" "); */                       
                                                 return                                     mat[m][n];                       
                                                 }                       
                                   
                                                 let T =                                     "ge"                                     ;                       
                                                 let S =                                     "geeksforgeeks"                                     ;                       
                                                 document.write(findSubsequenceCount(S, T));                       
                                   
                         </script>                       

输出：

复杂性分析：

时间复杂性： O（m*n）。只需要对矩阵进行一次遍历，因此时间复杂度为O（m*n）
辅助空间： O（m*n）。需要一个大小为m*n的矩阵，因此空间复杂度为O（m*n）。注：由于mat[i][j]只访问当前行和前一行的元素，我们只需使用两行就可以优化辅助空间，将空间从m*n减少到2*n。

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章