fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std; 
  3. const int MAX_CHAR = 256; 
  4.  
  5. // Returns count of distinct sunsequences of str. 
  6. int countSub(string str) 
  7. { 
  8.     // Create an array to store index 
  9.     // of last 
  10.     vector<int> last(MAX_CHAR, -1); 
  11.  
  12.     // Length of input string 
  13.     int n = str.length(); 
  14.  
  15.     // dp[i] is going to store count of distinct 
  16.     // subsequences of length i. 
  17.     int dp[n+1]; 
  18.  
  19.     // Empty substring has only one subsequence 
  20.     dp[0] = 1; 
  21.  
  22.     // Traverse through all lengths from 1 to n. 
  23.     for (int i=1; i<=n; i++) 
  24.     { 
  25.         // Number of subsequences with substring 
  26.         // str[0..i-1] 
  27.         dp[i] = 2*dp[i-1]; 
  28.  
  29.         // If current character has appeared 
  30.         // before, then remove all subsequences 
  31.         // ending with previous occurrence. 
  32.         if (last[str[i-1]] != -1) 
  33.             dp[i] = dp[i] - dp[last[str[i-1]]]; 
  34.  
  35.         // Mark occurrence of current character 
  36.         last[str[i-1]] = (i-1); 
  37.     } 
  38.  
  39.     return dp[n]; 
  40. } 
  41.  
  42. // Driver code 
  43. int main() 
  44. { 
  45.    cout << countSub("gfgg"); 
  46.    return 0; 
  47. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
https://ideone.com/M6Wqvq
language:
C++14 (gcc 8.3)
created:
4 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!