algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2250B)


      1 #include <vector>
      2 #include <iostream>
      3 #include <unordered_map>
      4 
      5 using namespace std;
      6 
      7 int main() {
      8 
      9     int l, r, n, q, testCases = 0;
     10     cin >> testCases;
     11 
     12     for(int z = 0; z < testCases; ++z) {
     13 
     14         cin >> n;
     15         cin >> q;
     16 
     17         string a,b  = "";
     18 
     19         cin >> a;
     20         cin >> b;
     21 
     22         // create prefix sum arrays per character
     23         // then use these to solve problems in O(1) time instead of O(r-l) time
     24 
     25         unordered_map<int, vector<int>> sumsA {};
     26         unordered_map<int, vector<int>> sumsB {};
     27         for(int ch = 0; ch < 26; ++ch) {
     28             sumsA[ch] = {};
     29             sumsB[ch] = {};
     30         }
     31 
     32         for(int i = 0; i < a.size(); ++i) {
     33             for(int ch = 0; ch < 26; ++ch) {
     34                 auto& currentCS = sumsA[ch];
     35                 if(i != 0) {
     36                     currentCS.push_back(currentCS[currentCS.size() - 1]);
     37                 } else {
     38                     currentCS.push_back(0);
     39                 }
     40             }
     41             auto ch = a[i] - 'a';
     42             sumsA[ch][sumsA[ch].size() -1] += 1;
     43         }
     44 
     45         for(int i = 0; i < a.size(); ++i) {
     46             for(int ch = 0; ch < 26; ++ch) {
     47                 auto& currentCS = sumsB[ch];
     48                 if(i != 0) {
     49                     currentCS.push_back(currentCS[currentCS.size() - 1]);
     50                 } else {
     51                     currentCS.push_back(0);
     52                 }
     53             }
     54             auto ch = b[i] - 'a';
     55             sumsB[ch][sumsB[ch].size() -1] += 1;
     56         }
     57 
     58         for(int qn = 0; qn < q; ++qn) {
     59             cin >> l;
     60             cin >> r;
     61 
     62             l -= 1;
     63             r -= 1;
     64 
     65             int intersection = 0;
     66 
     67             for(int ch = 0; ch < 26; ++ch) {
     68 
     69                 int av = 0;
     70                 int bv = 0;
     71 
     72                 if(l != 0) {
     73                     av = sumsA[ch][r] - sumsA[ch][l-1];
     74                 } else {
     75                     av = sumsA[ch][r] - 0;
     76                 }
     77 
     78                 if(l != 0) {
     79                     bv = sumsB[ch][r] - sumsB[ch][l-1];
     80                 } else {
     81                     bv = sumsB[ch][r] - 0;
     82                 }
     83 
     84                 intersection += std::min(av,bv);
     85             }
     86 
     87             cout << ((r-l) + 1) - intersection << endl;
     88         }
     89     }
     90 }