fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define __debug__
  6.  
  7. inline void debug( const string msg )
  8. {
  9. #ifdef __debug__
  10.     cout << msg << endl;
  11. #endif // __debug__
  12. }
  13.  
  14. inline string dp_str( const int i, const int j )
  15. {
  16.     return "dp["+to_string(i)+"]["+to_string(j)+"]";
  17. }
  18.  
  19. inline bool dp_value( const string msg, bool value = false )
  20. {
  21.     string ans[] = { "false", "true" };
  22.  
  23.     debug( msg + " is " + ans[value] );
  24.  
  25.     return value;
  26. }
  27.  
  28. struct stamp: vector<vector<bool>>
  29. {
  30.     int m, n, p, q; bool valid;
  31.  
  32.     void set( int i, int j )
  33.     {
  34.         at(i).at(j) = dp_value(dp_str(i,j),true);
  35.     }
  36.  
  37.     bool is_valid( int u, int v )
  38.     {
  39.         if ( at(u).at(v) )
  40.             return dp_value(dp_str(u,v),true);
  41.         else
  42.             dp_value(dp_str(u,v));
  43.  
  44.         if ( at(u).at(n) )
  45.             return dp_value(dp_str(u,n),true);
  46.         else
  47.             dp_value(dp_str(u,n));
  48.  
  49.         if ( v )
  50.             return dp_value("(v != 0)");
  51.  
  52.         for( int k = 1; k < n; k++ )
  53.             if ( at(u).at(k) )
  54.                 return dp_value(dp_str(u,k),true);
  55.  
  56.         return false;
  57.     }
  58.  
  59.     stamp( const string& s, const string& t): m(s.size()), n(t.size()), p(m+1), q(n+1), valid(false)
  60.     {
  61.         if ( s.front() != t.front() )
  62.         {
  63.             debug("first letter is different"); return;
  64.         }
  65.  
  66.         if ( s.back() != t.back() )
  67.         {
  68.             debug("last letter is different"); return;
  69.         }
  70.  
  71.         resize(p); for(auto& d: *this) d.resize(q,false); set(1,1);
  72.  
  73.         for( int u = 1, i = 2; u < m; u = i++ )
  74.             for( int v = 0, j = 1; v < n; v = j++ )
  75.                 if( s[u] == t[v] )
  76.                 {
  77.                     if ( is_valid(u,v) )
  78.                         set(i,j);
  79.                     else
  80.                         dp_value(dp_str(u,v));
  81.                 }
  82.                 else
  83.                     debug("s["+to_string(v)+"] != t["+to_string(v)+"]");
  84.  
  85.         valid = at(m).at(n);
  86.     }
  87. };
  88.  
  89. int main()
  90. {
  91.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  92.  
  93.     string s; cin >> s; set<string> substrings, solution; int m = s.size();
  94.  
  95.     debug("string length m = "+to_string(m));
  96.  
  97.     for( int i = 0, n = m + 1; i < m; i++, n-- )
  98.         for( int j = 1; j < n; j++ )
  99.         {
  100.             auto t = s.substr(i,j);
  101.  
  102.             debug("substring["+to_string(i)+","+to_string(j)+"]=\""+t+"\"");
  103.  
  104.             if ( substrings.find(t) == substrings.end() )
  105.             {
  106.                 substrings.insert(t);
  107.  
  108.                 if ( stamp(s,t).valid )
  109.                     solution.insert(t), debug("valid");
  110.                 else
  111.                     debug("invalid");
  112.             }
  113.             else
  114.                 debug("already checked");
  115.         }
  116.  
  117.     debug("solution:");
  118.  
  119.     for ( auto t: solution )
  120.         cout << t << endl;
  121. }
Success #stdin #stdout 0s 15264KB
comments (?)
stdin
copy 
babaaba
stdout
copy 
string length m = 7
substring[0,1]="b"
last letter is different
invalid
substring[0,2]="ba"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
dp[2][0] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
s[0] != t[0]
dp[4][1] is false
dp[4][2] is true
dp[5][2] is true
dp[5][0] is false
dp[5][2] is true
dp[6][1] is true
s[1] != t[1]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
valid
substring[0,3]="bab"
last letter is different
invalid
substring[0,4]="baba"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
s[2] != t[2]
dp[1][3] is false
dp[1][4] is false
(v != 0) is false
dp[1][3] is false
dp[2][0] is false
dp[2][4] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
dp[2][2] is true
dp[3][3] is true
s[3] != t[3]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
s[2] != t[2]
dp[3][3] is true
dp[4][4] is true
s[0] != t[0]
dp[4][1] is false
dp[4][4] is true
dp[5][2] is true
s[2] != t[2]
dp[4][3] is false
dp[4][4] is true
dp[5][4] is true
dp[5][0] is false
dp[5][4] is true
dp[6][1] is true
s[1] != t[1]
dp[5][2] is true
dp[6][3] is true
s[3] != t[3]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
s[2] != t[2]
dp[6][3] is true
dp[7][4] is true
valid
substring[0,5]="babaa"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
s[2] != t[2]
dp[1][3] is false
dp[1][5] is false
(v != 0) is false
dp[1][3] is false
dp[1][4] is false
dp[1][5] is false
(v != 0) is false
dp[1][4] is false
dp[2][0] is false
dp[2][5] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
dp[2][2] is true
dp[3][3] is true
s[3] != t[3]
s[4] != t[4]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
s[2] != t[2]
dp[3][3] is true
dp[4][4] is true
dp[3][4] is false
dp[3][5] is false
(v != 0) is false
dp[3][4] is false
s[0] != t[0]
dp[4][1] is false
dp[4][5] is false
(v != 0) is false
dp[4][1] is false
s[2] != t[2]
dp[4][3] is false
dp[4][5] is false
(v != 0) is false
dp[4][3] is false
dp[4][4] is true
dp[5][5] is true
dp[5][0] is false
dp[5][5] is true
dp[6][1] is true
s[1] != t[1]
dp[5][2] is false
dp[5][5] is true
dp[6][3] is true
s[3] != t[3]
s[4] != t[4]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
s[2] != t[2]
dp[6][3] is true
dp[7][4] is true
dp[6][4] is false
dp[6][5] is false
(v != 0) is false
dp[6][4] is false
invalid
substring[0,6]="babaab"
last letter is different
invalid
substring[0,7]="babaaba"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
s[2] != t[2]
dp[1][3] is false
dp[1][7] is false
(v != 0) is false
dp[1][3] is false
dp[1][4] is false
dp[1][7] is false
(v != 0) is false
dp[1][4] is false
s[5] != t[5]
dp[1][6] is false
dp[1][7] is false
(v != 0) is false
dp[1][6] is false
dp[2][0] is false
dp[2][7] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
dp[2][2] is true
dp[3][3] is true
s[3] != t[3]
s[4] != t[4]
dp[2][5] is false
dp[2][7] is false
(v != 0) is false
dp[2][5] is false
s[6] != t[6]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
s[2] != t[2]
dp[3][3] is true
dp[4][4] is true
dp[3][4] is false
dp[3][7] is false
(v != 0) is false
dp[3][4] is false
s[5] != t[5]
dp[3][6] is false
dp[3][7] is false
(v != 0) is false
dp[3][6] is false
s[0] != t[0]
dp[4][1] is false
dp[4][7] is false
(v != 0) is false
dp[4][1] is false
s[2] != t[2]
dp[4][3] is false
dp[4][7] is false
(v != 0) is false
dp[4][3] is false
dp[4][4] is true
dp[5][5] is true
s[5] != t[5]
dp[4][6] is false
dp[4][7] is false
(v != 0) is false
dp[4][6] is false
dp[5][0] is false
dp[5][7] is false
dp[5][5] is true
dp[6][1] is true
s[1] != t[1]
dp[5][2] is false
dp[5][7] is false
(v != 0) is false
dp[5][2] is false
s[3] != t[3]
s[4] != t[4]
dp[5][5] is true
dp[6][6] is true
s[6] != t[6]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
s[2] != t[2]
dp[6][3] is false
dp[6][7] is false
(v != 0) is false
dp[6][3] is false
dp[6][4] is false
dp[6][7] is false
(v != 0) is false
dp[6][4] is false
s[5] != t[5]
dp[6][6] is true
dp[7][7] is true
valid
substring[1,1]="a"
first letter is different
invalid
substring[1,2]="ab"
first letter is different
invalid
substring[1,3]="aba"
first letter is different
invalid
substring[1,4]="abaa"
first letter is different
invalid
substring[1,5]="abaab"
first letter is different
invalid
substring[1,6]="abaaba"
first letter is different
invalid
substring[2,1]="b"
already checked
substring[2,2]="ba"
already checked
substring[2,3]="baa"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
dp[1][2] is false
dp[1][3] is false
(v != 0) is false
dp[1][2] is false
dp[2][0] is false
dp[2][3] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
s[2] != t[2]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
dp[3][2] is false
dp[3][3] is false
(v != 0) is false
dp[3][2] is false
s[0] != t[0]
dp[4][1] is false
dp[4][3] is false
(v != 0) is false
dp[4][1] is false
dp[4][2] is true
dp[5][3] is true
dp[5][0] is false
dp[5][3] is true
dp[6][1] is true
s[1] != t[1]
s[2] != t[2]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
dp[6][2] is false
dp[6][3] is false
(v != 0) is false
dp[6][2] is false
invalid
substring[2,4]="baab"
last letter is different
invalid
substring[2,5]="baaba"
dp[1][1] is true
s[0] != t[0]
dp[1][1] is true
dp[2][2] is true
dp[1][2] is false
dp[1][5] is false
(v != 0) is false
dp[1][2] is false
s[3] != t[3]
dp[1][4] is false
dp[1][5] is false
(v != 0) is false
dp[1][4] is false
dp[2][0] is false
dp[2][5] is false
dp[2][2] is true
dp[3][1] is true
s[1] != t[1]
s[2] != t[2]
dp[2][3] is false
dp[2][5] is false
(v != 0) is false
dp[2][3] is false
s[4] != t[4]
s[0] != t[0]
dp[3][1] is true
dp[4][2] is true
dp[3][2] is false
dp[3][5] is false
(v != 0) is false
dp[3][2] is false
s[3] != t[3]
dp[3][4] is false
dp[3][5] is false
(v != 0) is false
dp[3][4] is false
s[0] != t[0]
dp[4][1] is false
dp[4][5] is false
(v != 0) is false
dp[4][1] is false
dp[4][2] is true
dp[5][3] is true
s[3] != t[3]
dp[4][4] is false
dp[4][5] is false
(v != 0) is false
dp[4][4] is false
dp[5][0] is false
dp[5][5] is false
dp[5][3] is true
dp[6][1] is true
s[1] != t[1]
s[2] != t[2]
dp[5][3] is true
dp[6][4] is true
s[4] != t[4]
s[0] != t[0]
dp[6][1] is true
dp[7][2] is true
dp[6][2] is false
dp[6][5] is false
(v != 0) is false
dp[6][2] is false
s[3] != t[3]
dp[6][4] is true
dp[7][5] is true
valid
substring[3,1]="a"
already checked
substring[3,2]="aa"
first letter is different
invalid
substring[3,3]="aab"
first letter is different
invalid
substring[3,4]="aaba"
first letter is different
invalid
substring[4,1]="a"
already checked
substring[4,2]="ab"
already checked
substring[4,3]="aba"
already checked
substring[5,1]="b"
already checked
substring[5,2]="ba"
already checked
substring[6,1]="a"
already checked
solution:
ba
baaba
baba
babaaba
https://ideone.com/vlT0YP
Stamp
language:
C++14 (gcc 8.3)
created:
5 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!