Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int INF = 1e9;
  6.  
  7. struct alah{
  8.     int i, j;
  9. };
  10.  
  11. bool equals(char a, char b){
  12.     return a == '?' || b == '?' || a == b;
  13. }
  14.  
  15. string update_str(string s){
  16.     string res = "";
  17.  
  18.     for(int i = 0; i < s.size(); i++){
  19.         if(s[i] == '?') res += 'a';
  20.         else if(s[i] != '*') res += s[i];
  21.     }
  22.  
  23.     return res;
  24. }
  25.  
  26. bool check(string & s1, string & s2){
  27.     vector<vector<int> > dp(s1.size() + 1, vector<int> (s2.size() + 1, INF));
  28.  
  29.     vector<int> pos1, pos2;
  30.  
  31.     for(int i = 0; i < s1.size(); i++){
  32.         if(s1[i] == '*')pos1.push_back(i);
  33.     }
  34.  
  35.     for(int j = 0; j < s2.size(); j++){
  36.         if(s2[j] == '*')pos2.push_back(j);
  37.     }
  38.  
  39.     int i = 0, j = 0;
  40.  
  41.     if(s1 == "*" || s2 == "*"){
  42.         if(s1 == "*" && s2 != s1){
  43.             s2 = update_str(s2);
  44.             s1 = s2;
  45.             cout << s2.size() << endl;
  46.             return true;
  47.         }
  48.  
  49.         if(s2 == "*" && s2 != s1){
  50.             s1 = update_str(s1);
  51.             s2 = s1;
  52.  
  53.             cout << s1.size();
  54.  
  55.             return true;
  56.         }
  57.  
  58.  
  59.         s1 = s2 = "";
  60.         cout << 0 << endl;
  61.         return true;
  62.     }
  63.  
  64.     if(i >= s1.size() || j >= s2.size()){
  65.         return false;
  66.     }
  67.  
  68.     if(equals(s1[i], s2[j])){
  69.         dp[i][j] = 1;
  70.     }
  71.  
  72.     if(s1[i] == '*' || s2[j] == '*'){
  73.         dp[i][j] = 1;
  74.     }
  75.  
  76.     if(s1[i] == '*' && s2[j] == '*'){
  77.         dp[i][j] == 0;
  78.     }
  79.  
  80.     queue<alah> q;
  81.  
  82.     q.push({i, j});
  83.  
  84.     while(!q.empty()){
  85.         int i = q.front().i,
  86.         j = q.front().j;
  87.  
  88.         q.pop();
  89.  
  90.         if(i + 1 > s1.size() || j + 1 > s2.size()) continue;
  91.  
  92.         int len = dp[i][j];
  93.  
  94.         int i1 = i + 1, j1 = j + 1;
  95.  
  96.         if(s1[i1] == '*'){
  97.             dp[i1][j1] = len + 1;
  98.             i1++;
  99.         }
  100.         if(s2[j1] == '*'){
  101.             dp[i1][j1] = len + 1;
  102.             j1++;
  103.         }
  104.  
  105.         if(j + 1 == s2.size()){
  106.             dp[i + 1][j] = len + 1;
  107.             q.push({i + 1, j});
  108.         }
  109.  
  110.         if(i + 1 == s1.size()){
  111.             dp[i][j + 1] = len + 1;
  112.             q.push({i, j + 1});
  113.         }
  114.  
  115.         if(i1 < s1.size() && j1 < s2.size() && equals(s1[i1], s2[j1])){
  116.             dp[i1][j1] = len + 1;
  117.             q.push({i1, j1});
  118.         }
  119.         int x = lower_bound(pos1.begin(), pos1.end(), i + 1) - pos1.begin() - 1;
  120.         int y = lower_bound(pos2.begin(), pos2.end(), j + 1) - pos2.begin() - 1;
  121.  
  122.         if(x >= 0 && dp[pos1[x]][j + 1] >= len + i - x){
  123.             dp[pos1[x]][j + 1] = len + i - x;
  124.  
  125.             q.push({pos1[x], j + 1});
  126.         }
  127.  
  128.         if(y >= 0 && dp[i + 1][pos2[y]] >= len + j - y){
  129.             dp[i + 1][pos2[y]] = len + j - y;
  130.  
  131.             q.push({i + 1, pos2[y]});
  132.         }
  133.  
  134.     }
  135.  
  136.     if(dp[s1.size() - 1][s2.size() - 1] != INF){
  137.         cout << s1 << " " << s2 << " " << dp[s1.size() - 1][s2.size() - 1] << endl;
  138.     }
  139.  
  140.     return (dp[s1.size() - 1][s2.size() - 1] != INF);
  141. }
  142.  
  143. int32_t main(){
  144.     string s1, s2;
  145.  
  146.     cin >> s1 >> s2;
  147.  
  148.     cout << check(s1, s2) << endl;
  149. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top