MarioYC

Equivalent Suffix Tries - Test case generator

Jul 11th, 2012
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. // Tree isomorphism
  10. map< vector<int> , int > M;
  11. string S;
  12. int cont;
  13.  
  14. int hash(int l, int r){
  15.     vector<int> v;
  16.     v.push_back(0);
  17.    
  18.     int aux = 0;
  19.    
  20.     for(int i = l,x = l;i <= r;++i){
  21.         if(S[i] == '0') ++aux;
  22.         else --aux;
  23.        
  24.         if(aux == 0){
  25.             v.push_back(hash(x + 1,i - 1));
  26.             x = i + 1;
  27.         }
  28.     }
  29.    
  30.     if(v.size() > 1) sort(v.begin() + 1,v.end());
  31.     v.push_back(1);
  32.    
  33.     if(M.find(v) == M.end()) M[v] = cont++;
  34.    
  35.     return M[v];
  36. }
  37.  
  38.  
  39. // Trie
  40. int next[10000][10],cont2;
  41.  
  42. void add(string s){
  43.     int L = s.size();
  44.     int pos = 0;
  45.    
  46.     for(int i = 0;i < L;++i){
  47.         if(next[pos][ s[i] - 'a' ] == -1)
  48.             next[pos][ s[i] - 'a' ] = cont2++;
  49.        
  50.         pos = next[pos][ s[i] - 'a' ];
  51.     }
  52. }
  53.  
  54. int B,L;
  55.  
  56. // Trie into string
  57. string dfs(int pos){
  58.     string ret = "0";
  59.    
  60.     for(int i = 0;i < B;++i){
  61.         if(next[pos][i] != -1){
  62.             ret += "0";
  63.             ret += dfs(next[pos][i]);
  64.             ret += "1";
  65.         }
  66.     }
  67.    
  68.     ret += "1";
  69.    
  70.     return ret;
  71. }
  72.  
  73. int main(){
  74.     //B : numer of different characters
  75.     //L : length of the strings
  76.     cin >> B >> L;
  77.    
  78.     string s;
  79.     cont = 2;
  80.    
  81.     vector<string> v;
  82.     v.push_back("");
  83.    
  84.     for(int i = 0;i < L;++i){
  85.         int L2 = v.size();
  86.        
  87.         for(int j = 1;j < B;++j)
  88.             for(int k = 0;k < L2;++k)
  89.                 v.push_back(v[k]);
  90.        
  91.         for(int j = 0,k = 0;j < B;++j)
  92.             for(int x = 0;x < L2;++x)
  93.                 v[k++] += (char)('a' + j);
  94.     }
  95.    
  96.     vector< pair<int,string> > H;
  97.    
  98.     bool have[26];
  99.    
  100.     for(int i = 0;i < v.size();++i){
  101.         string s = v[i];
  102.        
  103.         memset(have,false,sizeof have);
  104.         int alph = 0;
  105.         bool ok = true;
  106.        
  107.         for(int j = 0;j < L;++j){
  108.             if(!have[ s[j] - 'a' ]){
  109.                 if(s[j] - 'a' != alph) ok = false;
  110.                 have[ s[j] - 'a' ] = true;
  111.                 ++alph;
  112.             }
  113.         }
  114.        
  115.         if(alph < B || !ok) continue;
  116.        
  117.         memset(next,-1,sizeof next);
  118.         cont2 = 1;
  119.        
  120.         string s2;
  121.        
  122.         for(int j = L - 1;j >= 0;--j){
  123.             s2 = s[j] + s2;
  124.             add(s2);
  125.         }
  126.        
  127.         string ret = dfs(0);
  128.         S = ret;
  129.         int ret2 = hash(0,ret.size() - 1);
  130.         H.push_back(make_pair(ret2,s));
  131.     }
  132.    
  133.     sort(H.begin(),H.end());
  134.    
  135.     cout << H.size() << endl;
  136.    
  137.     for(int i = 0;i < H.size();){
  138.         int e = i;
  139.        
  140.         while(e < H.size() && H[e].first == H[i].first) ++e;
  141.        
  142.         for(int j = i;j < e;++j)
  143.             cout << H[j].second << " " << e - i << endl;
  144.        
  145.        
  146.         i = e;
  147.     }
  148.    
  149.     return 0;
  150. }
RAW Paste Data