fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (long long i = a; i <= b; i++)
  5. #define REP(i, n) for (long long i = 0; i < n; i++)
  6. #define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
  7. #define fill(ar, val) memset(ar, val, sizeof(ar))
  8. #define PI 3.1415926535897932385
  9. #define uint64 long long
  10. #define int64 long long
  11. #define all(ar) ar.begin(), ar.end()
  12. #define pb push_back
  13. #define ff first
  14. #define ss second
  15. #define bit(n) (1<<(n))
  16. #define Last(i) ( (i) & (-i) )
  17. #define sq(x) ((x) * (x))
  18. #define mp make_pair
  19. #define pb push_back
  20. #define MOD 1000000007
  21. #define s arr[i]
  22. string a , b, c, d;
  23. vector<string> arr(4);
  24. int nxt[4][50][26];
  25. long long dp[50][50][50][50][26];
  26. bool visit [ 50 ][50][50][50][26];
  27. void precompute ()
  28.  {
  29.    for( int i = 0 ; i  < 4 ; i ++ )    // Repeating for all strings
  30.      for ( int z = 0 ; z< 26 ; z++ )   // Repeating for all characters
  31.         for(  int j = s.length() - 1 , idx = -1  ; j  >= 0 ; j -- )
  32.             {
  33.                int ch = s[j]-'a' ;
  34.  
  35.  
  36.                if( ch  == z )
  37.                  idx =  j ;
  38.  
  39.                 nxt[i][j][z]  = idx ; // next occurance of zth character after index j in i-th string is  = next[i][j][z] ;
  40.  
  41.  
  42.             }
  43.  
  44.  
  45.  }
  46.  
  47.  long long rec ( int i , int j ,  int k ,  int l ,  int alp )
  48.     {
  49.         if( i ==  -1 || j == -1 || k == -1 || l == -1 )
  50.               return 0 ;
  51.  
  52.         if( i >= arr[0].length() || j >= arr[1].length() || k >=  arr[2].length() || l >= arr[3].length() )
  53.               return 0 ;
  54.  
  55.         i = nxt[0][i][alp] ; j =  nxt[1][j][alp] ; k =  nxt[2][k][alp] ; l = nxt[3][l][alp] ;
  56.  
  57.           if( i ==  -1 || j == -1 || k == -1 || l == -1 )
  58.               return 0 ;
  59.  
  60.        if( visit[i][j][k][l][alp] )
  61.           return dp[i][j][k][l][alp];
  62.  
  63.        int u1 = arr[0][i] - 'a';
  64.        int u2 = arr[1][j] - 'a';
  65.        int u3 = arr[2][k] - 'a';
  66.        int u4 = arr[3][l] - 'a';
  67.  
  68.        if( u1 == alp && u2 == alp && u3 == alp && u4 == alp )
  69.         {
  70.           long long  sum = 1;
  71.            for( int  idx = 0 ; idx  < 26 ; idx ++ )
  72.              {// cout<< nxt[0][i][idx] << nxt[1][j][idx] <<  nxt[2][k][idx] << nxt[3][l][idx]<<endl;
  73.                sum+=rec( i+1 , j+1 , k+1  , l + 1  , idx  );
  74.  
  75.               }
  76.  
  77.  
  78.            visit[i][j][k][l][alp] = true;
  79.            dp[i][j][k][l][alp] = sum ;
  80.  
  81.            return sum  ;
  82.  
  83.         }
  84.  
  85.  
  86.     }
  87.  
  88. int  main( )
  89. {
  90.  // ios::sync_with_stdio( 0 );
  91.  // cin.tie(0);
  92.   for( int i = 0 ; i  < 4 ; i ++  )
  93.     cin >> arr[i];
  94.  
  95.  
  96.     precompute();
  97.  
  98.    long long sum = 0 ;
  99.    for( int i = 0 ; i < 26 ; i ++ )
  100.       sum += rec( 0 , 0,  0 ,0 , i );
  101.  
  102.  
  103.     cout<<sum<<endl;
  104. }
  105.  
  106.  
Runtime error #stdin #stdout 0s 100KB
comments (?)
stdin 
aabb
abab
baba
acba
stdout 
Standard output is empty
https://ideone.com/AvliD4
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!