fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main(int argc, char* argv[]) {
  6.   vector<int> doc = {
  7.     2, 5, 1, 3, 5, 2, 2, 5, 3, 2, 2, 1,
  8.   };
  9.  
  10.   vector<vector<int>> occ = {
  11.     {2, 11},
  12.     {0, 5, 6, 9, 10},
  13.     {3, 8},
  14.   };
  15.  
  16.   for (int i = 0; i < doc.size(); ++ i) {
  17.     doc[i] = -1;
  18.   }
  19.  
  20.   for (int i = 0; i < occ.size(); ++ i) {
  21.     for (int j = 0; j < occ[i].size(); ++ j) {
  22.       doc[occ[i][j]] = i;
  23.     }
  24.   }
  25.  
  26.   int lbound = doc.size();
  27.   int rbound = 0;
  28.  
  29.   for (int i = 0; i < occ.size(); ++ i) {
  30.     if (lbound > occ[i][0]) {
  31.       lbound = occ[i][0];
  32.     }
  33.  
  34.     if (rbound < occ[i][0]) {
  35.       rbound = occ[i][0];
  36.     }
  37.   }
  38.  
  39.   int minWindowSize = doc.size();
  40.   vector<int> index(occ.size(), 0);
  41.   for (; lbound < occ.size(); ++ lbound) {
  42.     if (minWindowSize > rbound - lbound + 1) {
  43.       minWindowSize = rbound - lbound + 1;
  44.     }
  45.  
  46.     int word = doc[lbound];
  47.  
  48.     if (word == -1) {
  49.       continue;
  50.     }
  51.  
  52.     index[word] ++;
  53.     if (occ[word].size() == index[word]) {
  54.       break;
  55.     }
  56.  
  57.     if (rbound < occ[word][index[word]]) {
  58.       rbound = occ[word][index[word]];
  59.     }
  60.   }
  61.  
  62.   cout << minWindowSize << endl;
  63.   return 0;
  64. }
  65.  
  66.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/p6STMv
language:
C++14 (gcc 8.3)
created:
12 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!