fork download 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. int numDistinct(string S, string T) {
  7. 	//corner cases
  8. 	if (!S.size() || !T.size() || S.size() < T.size()) return 0;
  9.  
  10. 	//state counter array
  11. 	int* ct = new int[T.size()]();
  12. 	ct[0] = 1;
  13. 	int ret = 0;
  14. 	for (int i = 0; i<S.size(); i++)
  15. 		for (int j = T.size() - 1; j >= 0; j--)
  16. 			if (S[i] == T[j])
  17. 				if (j == T.size() - 1) ret += ct[j];
  18. 				else ct[j + 1] += ct[j];
  19.  
  20. 	return ret;
  21. }
  22.  
  23. int main() {
  24. 	string S = "rabbbit";
  25. 	string T = "rabbit";
  26.  
  27. 	int ret;
  28. 	ret = numDistinct(S, T);
  29.  
  30. 	cout << ret;
  31.  
  32. 	return 0;
  33. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin 
Standard input is empty
stdout 
3
https://ideone.com/jk4EEA
Distinct subsequence code for my blog
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!