fork download
copy 
  1. // CECR 2012
  2. // Problem E: Word Equations
  3. // Correct solution, O(kp)
  4. // Author: Grzegorz Herman
  5.  
  6. #include <cassert>
  7. #include <iostream>
  8. #include <map>
  9. #include <string>
  10. #include <vector>
  11. using namespace std;
  12.  
  13. const int MAXK = 1000;
  14. const int MAXS = 5;
  15. const int MAXT = 5000;
  16.  
  17. struct eq
  18. {
  19.     string      s[2];
  20.     eq *        e[2];
  21.     vector<int> b;
  22.  
  23.     eq(string s0="", string s1="")
  24.     {
  25.         s[0] = s0; s[1] = s1;
  26.         e[0] = e[1] = 0;
  27.     }
  28.  
  29.     int term(string const & p, int j)
  30.     {
  31.         int maxi = s[0].length();
  32.         int maxj = p.length();
  33.         for (int i=0; i<maxi && j<maxj; ++i)
  34.             if (s[0][i] == p[j])
  35.                 ++j;
  36.         return j;
  37.     }
  38.  
  39.     int best(string const & p, int j)
  40.     {
  41.     	//cout << s[0] << " " << s[1] << " " << j << endl;
  42.         if (b.empty()) b.resize(p.length()+1, -1);
  43.         //if(b[j]>=0) cout << "dp : " << s[0] << " " << s[1] << " " << j << endl;
  44.         return b[j] = (b[j]>=0) ? b[j] : e[1] ? e[1]->best(p, e[0]->best(p, j)) : term(p, j);
  45.        // return e[1] ? e[1]->best(p, e[0]->best(p, j)) : term(p, j);
  46.     }
  47. };
  48.  
  49. int main()
  50. {
  51.     int z; for (cin >> z; z; --z)
  52.     {
  53.         map<string, eq> M;
  54.         string s[3], t, p;
  55.         int k; for (cin >> k; k; --k)
  56.         {
  57.             cin >> s[2] >> s[1] >> s[0];
  58.             if (s[0][0]<='Z') cin >> s[1] >> s[1];
  59.             M[s[2]] = eq(s[0], s[1]);
  60.         }
  61.         for (map<string, eq>::iterator i = M.begin(); i != M.end(); ++i)
  62.             if (i->second.s[0][0]<='Z')
  63.                 for (int k=0; k<2; ++k)
  64.                     i->second.e[k] = &M[i->second.s[k]];
  65.         cin >> t >> p;
  66.         cout << (M[t].best(p, 0) < p.length() ? "NO" : "YES") << endl;
  67.     }
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
1
6
CACA = ca
CACB = cb
CADA = da
CBCA = CACA + CACB
CBCB = CACA + CADA
DACA = CBCA + CBCB
DACA
dacbca
stdout
copy 
NO
https://ideone.com/lJSpqM
language:
C++14 (gcc 8.3)
created:
2 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!