给两条线 str1 和 str2 长度 n1 和 n2 分别地问题是计算所有的子序列 str1 这些是 str2 . 例如：
null
Input : str1 = "abacd", str2 = "abc"Output : 2Index of characters in the 2 subsequences are:{0, 1, 3} = {a, b, c} = abc and{1, 2, 3} = {b, a, c} = bacThe above two subsequences of str1 are anagrams of str2.Input : str1 = "geeksforgeeks", str2 = "geeks" Output : 48
方法： 创建两个数组 频率1[] 和 频率2[] 大小为“26”的每个字符都实现为哈希表，以存储每个字符的频率 str1 和 str2 分别地允许 n1 和 n2 长度 str1 和 str2 分别地现在实现以下算法：
countSubsequences(str1, str2) for i = 0 to n1-1 freq1[str1[i] - 'a']++ for i = 0 n2-1 freq2[str2[i] - 'a']++ Initialize count = 1 for i = 0 to 25 if freq2[i] != 0 then if freq2[i] <= freq1[i] then count = count * binomialCoeff(freq1[i], freq2[i]) else return 0 return count
设freq1[i]表示为 N 而freq2[i]as R 现在 比诺米亚尔科夫（北，右） 上面提到的算法就是二项式系数 N C R 参考 这 为其实施发布。 说明： 让某些字符的频率表示 中国 在’str2’中是’x’，’str1’中是’y’。如果y
C++
// C++ implementation to // count subsequences in // first string which are // anagrams of the second // string #include <bits/stdc++.h> using namespace std; #define SIZE 26 // Returns value of Binomial // Coefficient C(n, k) int binomialCoeff( int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ( int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // function to count subsequences // in first string which are // anagrams of the second string int countSubsequences(string str1, string str2) { // hash tables to store frequencies // of each character int freq1[SIZE], freq2[SIZE]; int n1 = str1.size(); int n2 = str2.size(); // Initialize memset (freq1, 0, sizeof (freq1)); memset (freq2, 0, sizeof (freq2)); // store frequency of each // character of 'str1' for ( int i = 0; i < n1; i++) freq1[str1[i] - 'a' ]++; // store frequency of each // character of 'str2' for ( int i = 0; i < n2; i++) freq2[str2[i] - 'a' ]++; // to store the total count // of subsequences int count = 1; for ( int i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // if this character's frequency // in 'str2' in less than or // equal to its frequency in // 'str1' then accumulate its // contribution to the count // of subsequences. If its // frequency in 'str1' is 'n' // and in 'str2' is 'r', then // its contribution will be nCr, // where C is the binomial // coefficient. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count; } // Driver program to test above int main() { string str1 = "abacd" ; string str2 = "abc" ; cout << "Count = " << countSubsequences(str1, str2); return 0; } |
JAVA
// Java implementation to // count subsequences in // first string which are // anagrams of the second // string import java.util.*; import java.lang.*; public class GfG{ public final static int SIZE = 26 ; // Returns value of Binomial // Coefficient C(n, k) public static int binomialCoeff( int n, int k) { int res = 1 ; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ( int i = 0 ; i < k; ++i) { res *= (n - i); res /= (i + 1 ); } return res; } // function to count subsequences // in first string which are // anagrams of the second string public static int countSubsequences(String str, String str3) { // hash tables to store frequencies // of each character int [] freq1 = new int [SIZE]; int [] freq2 = new int [SIZE]; char [] str1 = str.toCharArray(); char [] str2 = str3.toCharArray(); int n1 = str.length(); int n2 = str3.length(); // store frequency of each // character of 'str1' for ( int i = 0 ; i < n1; i++) freq1[str1[i] - 'a' ]++; // store frequency of each // character of 'str2' for ( int i = 0 ; i < n2; i++) freq2[str2[i] - 'a' ]++; // to store the total count // of subsequences int count = 1 ; for ( int i = 0 ; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0 ) { // if this character's frequency // in 'str2' in less than or // equal to its frequency in // 'str1' then accumulate its // contribution to the count // of subsequences. If its // frequency in 'str1' is 'n' // and in 'str2' is 'r', then // its contribution will be nCr, // where C is the binomial // coefficient. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0 ; } // required count of subsequences return count; } // Driver function public static void main(String argc[]) { String str1 = "abacd" ; String str2 = "abc" ; System.out.println( "Count = " + countSubsequences(str1, str2)); } } /* This code is contributed by Sagar Shukla */ |
python
# Python3 implementation to count # subsequences in first which are # anagrams of the second # import library import numpy as np SIZE = 26 # Returns value of Binomial # Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k # Calculate value of # [n * (n-1) *---* (n-k+1)] / # [k * (k-1) *----* 1] for i in range ( 0 , k): res = res * (n - i) res = int (res / (i + 1 )) return res # Function to count subsequences # in first which are anagrams # of the second def countSubsequences(str1, str2): # Hash tables to store frequencies # of each character freq1 = np.zeros( 26 , dtype = np. int ) freq2 = np.zeros( 26 , dtype = np. int ) n1 = len (str1) n2 = len (str2) # Store frequency of each # character of 'str1' for i in range ( 0 , n1): freq1[ ord (str1[i]) - ord ( 'a' ) ] + = 1 # Store frequency of each # character of 'str2' for i in range ( 0 , n2): freq2[ ord (str2[i]) - ord ( 'a' )] + = 1 # To store the total count # of subsequences count = 1 for i in range ( 0 , SIZE): # if character (i + 'a') # exists in 'str2' if (freq2[i] ! = 0 ): # if this character's frequency # in 'str2' in less than or # equal to its frequency in # 'str1' then accumulate its # contribution to the count # of subsequences. If its # frequency in 'str1' is 'n' # and in 'str2' is 'r', then # its contribution will be nCr, # where C is the binomial # coefficient. if (freq2[i] < = freq1[i]): count = count * binomialCoeff(freq1[i], freq2[i]) # else return 0 as there could # be no subsequence which is an # anagram of 'str2' else : return 0 # required count of subsequences return count # Driver code str1 = "abacd" str2 = "abc" ans = countSubsequences(str1, str2) print ( "Count = " , ans) # This code contributed by saloni1297 |
C#
// C# implementation to // count subsequences in // first string which are // anagrams of the second // string using System; class GfG { public static int SIZE = 26; // Returns value of Binomial // Coefficient C(n, k) public static int binomialCoeff( int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ( int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // function to count subsequences // in first string which are // anagrams of the second string public static int countSubsequences(String str, String str3) { // hash tables to store frequencies // of each character int [] freq1 = new int [SIZE]; int [] freq2 = new int [SIZE]; char [] str1 = str.ToCharArray(); char [] str2 = str3.ToCharArray(); int n1 = str.Length; int n2 = str3.Length; // store frequency of each // character of 'str1' for ( int i = 0; i < n1; i++) freq1[str1[i] - 'a' ]++; // store frequency of each // character of 'str2' for ( int i = 0; i < n2; i++) freq2[str2[i] - 'a' ]++; // to store the total count // of subsequences int count = 1; for ( int i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // if this character's frequency // in 'str2' in less than or // equal to its frequency in // 'str1' then accumulate its // contribution to the count // of subsequences. If its // frequency in 'str1' is 'n' // and in 'str2' is 'r', then // its contribution will be nCr, // where C is the binomial // coefficient. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count; } // Driver code public static void Main(String[] argc) { String str1 = "abacd" ; String str2 = "abc" ; Console.Write( "Count = " + countSubsequences(str1, str2)); } } // This code is contributed by parashar |
PHP
<?php // PHP implementation to // count subsequences in // first $which are // anagrams of the second // string $SIZE = 26; // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff( $n , $k ) { $res = 1; // Since C(n, k) = C(n, n-k) if ( $k > $n - $k ) $k = $n - $k ; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ( $i = 0; $i < $k ; ++ $i ) { $res *= ( $n - $i ); $res /= ( $i + 1); } return $res ; } // function to count // subsequences in // first string which // are anagrams of the // second string function countSubsequences( $str1 , $str2 ) { global $SIZE ; // hash tables to // store frequencies // of each character $freq1 = array (); $freq2 = array (); // Initialize for ( $i = 0; $i < $SIZE ; $i ++) { $freq1 [ $i ] = 0; $freq2 [ $i ] = 0; } $n1 = strlen ( $str1 ); $n2 = strlen ( $str2 ); // store frequency of each // character of 'str1' for ( $i = 0; $i < $n1 ; $i ++) $freq1 [ord( $str1 [ $i ]) - ord( 'a' )]++; // store frequency of each // character of 'str2' for ( $i = 0; $i < $n2 ; $i ++) $freq2 [ord( $str2 [ $i ]) - ord( 'a' )]++; // to store the total count // of subsequences $count = 1; for ( $i = 0; $i < $SIZE ; $i ++) // if character (i + 'a') // exists in 'str2' if ( $freq2 [ $i ] != 0) { // if this character's frequency // in 'str2' in less than or // equal to its frequency in // 'str1' then accumulate its // contribution to the count // of subsequences. If its // frequency in 'str1' is 'n' // and in 'str2' is 'r', then // its contribution will be nCr, // where C is the binomial // coefficient. if ( $freq2 [ $i ] <= $freq1 [ $i ]) $count = $count * binomialCoeff( $freq1 [ $i ], $freq2 [ $i ]); // else return 0 as there // could be no subsequence // which is an anagram of // 'str2' else return 0; } // required count // of subsequences return $count ; } // Driver Code $str1 = "abacd" ; $str2 = "abc" ; echo ( "Count = " . countSubsequences( $str1 , $str2 )); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Javascript
<script> // JavaScript implementation to // count subsequences in // first string which are // anagrams of the second // string var SIZE = 26 // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff(n, k) { var res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ( var i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // function to count subsequences // in first string which are // anagrams of the second string function countSubsequences(str1, str2) { // hash tables to store frequencies // of each character var freq1 = Array(SIZE).fill(0), freq2 = Array(SIZE).fill(0); var n1 = str1.length; var n2 = str2.length; // store frequency of each // character of 'str1' for ( var i = 0; i < n1; i++) freq1[str1[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // store frequency of each // character of 'str2' for ( var i = 0; i < n2; i++) freq2[str2[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // to store the total count // of subsequences var count = 1; for ( var i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // if this character's frequency // in 'str2' in less than or // equal to its frequency in // 'str1' then accumulate its // contribution to the count // of subsequences. If its // frequency in 'str1' is 'n' // and in 'str2' is 'r', then // its contribution will be nCr, // where C is the binomial // coefficient. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count; } // Driver program to test above var str1 = "abacd" ; var str2 = "abc" ; document.write( "Count = " + countSubsequences(str1, str2)); </script> |
输出：
Count = 2
时间复杂性： O（n1+n2）+O（最大值），其中 最大值 是最大频率。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
