ccbeginner

ZJ b397

Feb 12th, 2020
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ZJ b397
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct stat{
  6.     int x, y;
  7.     string cur;
  8.     bool operator<(const stat &rhs)const{
  9.         if(x != rhs.x)return x < rhs.x;
  10.         if(y != rhs.y)return y < rhs.y;
  11.         return cur < rhs.cur;
  12.     }
  13. };
  14.  
  15. int dp[33][33];
  16. string s1,s2;
  17. set<string> v;
  18. set<stat> vis;
  19.  
  20. void dfs(int x, int y, string cur){
  21.     if(cur.size() + dp[x][y] < dp[0][0])return;
  22.     stat tmd = {.x = x, .y = y, .cur = cur};
  23.     if(vis.find(tmd) != vis.end())return;
  24.     else vis.insert(tmd);
  25.     //cout << x << ' ' << y << ' ' <<cur << endl;
  26.     if(cur.size() == dp[0][0]){
  27.         v.insert(cur);
  28.     }else{
  29.         if(s1[x] == s2[y])dfs(x+1, y+1, cur+s1[x]);
  30.         else{
  31.             dfs(x, y+1, cur);
  32.             dfs(x+1, y, cur);
  33.         }
  34.     }
  35. }
  36.  
  37. int32_t main(){
  38.     int t;
  39.     cin >> t;
  40.     for(int k = 1; k <= t; ++k){
  41.         v.clear();
  42.         vis.clear();
  43.         memset(dp, 0, sizeof(dp));
  44.         cin >> s1 >> s2;
  45.         for(int i = s1.size()-1; i >= 0; --i){
  46.             for(int j = s2.size()-1; j >= 0; --j){
  47.                 if(s1[i] == s2[j])dp[i][j] = dp[i+1][j+1] + 1;
  48.                 else dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
  49.             }
  50.         }
  51.         dfs(0, 0, "");
  52.         printf("Case #%d: %d\n", k, v.size());
  53.         for(auto it = v.begin(); it != v.end(); ++it)cout << (*it) << '\n';
  54.     }
  55.     return 0;
  56. }
RAW Paste Data