fork download
copy 
  1. /**
  2.  * April 2013 Long Challenge at Codechef
  3.  *
  4.  * Problem:     STRQUERY - String Query
  5.  * Author:      Anton Lunyov (Editorialist)
  6.  * Complexity:  O(Q * log^2 Q + (sum of |q|) * log Q)
  7.  * Timing:      0.80 out of 1.00
  8.  *
  9.  * Variable or method names in comments
  10.  * are sometimes surrounded by grave accent signs, like `q`.
  11.  */
  12. #include <vector>
  13. #include <string>
  14. #include <cstring>
  15. #include <cstdlib>
  16. #include <algorithm>
  17. using namespace std;
  18.  
  19. // Supports the following types of queries on the string S:
  20. // - match(q) - returns the number of occurrences of the string `q` in S,
  21. //              complexity is O(|q| * log |S|).
  22. // - pop()    - deletes the first character of S and returns its value,
  23. //              complexity is O(log |S|).
  24. // - push(c)  - inserts character `c` at the beginning of the string,
  25. //              complexity is O(log^2 |S|).
  26. // - size()   - returns the length of the string,
  27. //              complexity is O(1).
  28. // - at(i)    - returns the i-th character of S in 0-based numeration,
  29. //              complexity is O(1).
  30. // - revat(i) - returns the i-th character of S reversed (in 0-based numeration),
  31. //              it will be convenient for the main class StringDeque,
  32. //              complexity is O(1).
  33. // Occupies O(|S|) memory at each moment.
  34. class DynamicSuffixArray {
  35.  private:
  36.   // The data structure for node of the treap.
  37.   struct Node {
  38.     int left, right, parent;
  39.     int size;  // The size of the subtree.
  40.     int y;     // The key for heap ordering.
  41.  
  42.     // Creates node having all zero links, but with size 1.
  43.     // We will call such node as default node.
  44.     // rand() for y keeps the tree self-balancing.
  45.     Node(): y(rand()), left(0), right(0), parent(0), size(1) {};
  46.   };
  47.  
  48.   // Node nodes_[id] corresponds to the suffix that starts at str_[id].
  49.   vector<char> str_;    // The actual string in reversed order.
  50.   vector<Node> nodes_;  // The nodes of the treap.
  51.   int root_;            // nodes_[root_] is the root of the treap.
  52.  
  53.  public:
  54.   // Creates dummy zero character and zero node, and sets root to 0.
  55.   DynamicSuffixArray() {
  56.     str_.push_back(0);
  57.     nodes_.push_back(Node());
  58.     nodes_[0].size = 0;  // The size is 1 by default so we fix this.
  59.     root_ = 0;           // Indicates that the tree is empty.
  60.   }
  61.   // To construct dynamic suffix array by string we should push all characters
  62.   // of the string in reversed order. So complexity is O(|S| * log^2 |S|).
  63.   // TODO: Implement a constructor by string using usual suffix array
  64.   // with complexity O(|S| * log |S|) or even O(|S|).
  65.  
  66.   // Returns the number of occurrences of the string `q` in the string S.
  67.   int match(const string& q) {
  68.     return match(root_, q, false, false);
  69.   }
  70.  
  71.   // Deletes the first character of the string and returns its value.
  72.   char pop() {
  73.     remove(size());  // Removes last node from the tree and updates the root.
  74.     nodes_.pop_back();
  75.     char c = str_.back();
  76.     str_.pop_back();
  77.     return c;
  78.   }
  79.  
  80.   // Inserts character `c` to the beginning of the string.
  81.   void push(char c) {
  82.     str_.push_back(c);         // We add `c` to the array `str_`.
  83.     nodes_.push_back(Node());  // We add default node to the array `nodes_`...
  84.     // ...and then actually insert this node to the tree and update the root.
  85.     root_ = insert(root_, size());
  86.   }
  87.  
  88.   // Returns the length of the string.
  89.   int size() {
  90.     return str_.size() - 1;  // "-1" because of the dummy zero character.
  91.   }
  92.  
  93.   // Returns the i-th character of the string in 0-based numeration.
  94.   char at(int i) {
  95.     // Recall that the 0-th character of S is `size()`-th character in `str_`.
  96.     return str_[size() - i];
  97.   }
  98.  
  99.   // Returns the i-th character of the reversed string in 0-based numeration.
  100.   char revat(int i) {
  101.     return str_[i + 1];  // "+1" because of the dummy zero character.
  102.   }
  103.  
  104.  private:
  105.   // See editorial for details.
  106.   int match(int tree, const string& q, bool matchLeft, bool matchRight) {
  107.     // For empty subtree the answer is 0.
  108.     if (!tree) {
  109.       return 0;
  110.     }
  111.     // In this case all suffixes in subtree start with `q`.
  112.     if (matchLeft && matchRight) {
  113.       // So the answer is the size of this subtree.
  114.       return nodes_[tree].size;
  115.     }
  116.     for (int i = 0; i < q.size(); ++i) {
  117.       if (q[i] > str_[tree - i]) {
  118.         // Here `matchLeft` should be set to false.
  119.         return match(nodes_[tree].right, q, false, matchRight);
  120.       } else if (q[i] < str_[tree - i]) {
  121.         // While here `matchRight` should be set to false.
  122.         return match(nodes_[tree].left, q, matchLeft, false);
  123.       }
  124.     }
  125.     return 1 +
  126.       match(nodes_[tree].left, q, matchLeft, true) +
  127.       match(nodes_[tree].right, q, true, matchRight);
  128.   }
  129.  
  130.   // Sets parent of node `id` to `parent_id` if `id` is non-zero.
  131.   void setParent(int id, int parent_id) {
  132.     if (id) {
  133.       nodes_[id].parent = parent_id;
  134.     }
  135.   }
  136.  
  137.   // Sets field `size` of the node `id` to the actual size of its subtree.
  138.   // Modifies only non-zero nodes.
  139.   void fixSize(int id) {
  140.     if (id) {
  141.       nodes_[id].size = 1 + 
  142.         nodes_[nodes_[id].left].size +
  143.         nodes_[nodes_[id].right].size;
  144.     }
  145.   }
  146.  
  147.   // Removes node `id` from the tree and update the root.
  148.   // Vector `nodes_` does not change.
  149.   void remove(int id) {
  150.     int par = nodes_[id].parent;
  151.     int tmp = merge(nodes_[id].left, nodes_[id].right);
  152.     // `tmp` is id of node that contains merge of children of the node `id`.
  153.     // `par` is the parent of `tmp` since `tmp` is replacement of `id`.
  154.     setParent(tmp, par);
  155.     if (par) {
  156.       // If `id` has parent then root remains the same,
  157.       // but we need to replace `id` by `tmp` in sons of the node `par`.
  158.       if(nodes_[par].left == id) {
  159.         nodes_[par].left = tmp;
  160.       } else {
  161.         nodes_[par].right = tmp;
  162.       }
  163.       while (par) {
  164.         // Since we delete one node in subtree of `id`,
  165.         // we should decrease the field `size` of each its ancestor by 1.
  166.         nodes_[par].size--;
  167.         par = nodes_[par].parent;
  168.       }
  169.     } else {
  170.       // Otherwise `id` was the root and the new root is `tmp`.
  171.       root_ = tmp;
  172.     }
  173.   }
  174.  
  175.   // Merges subtrees rooted at `L` and `R` and save result in one of the them.
  176.   // Each node in the subtree rooted at `L` should be less than
  177.   // each node in the subtree rooted at `R`.
  178.   int merge(int L, int R) {
  179.     // We return L when R is 0 and R when L is 0.
  180.     if (!L || !R) {
  181.       return L + R;
  182.     }
  183.     // We should preserve the heap property by field `y`.
  184.     if (nodes_[L].y < nodes_[R].y) {
  185.       // In this case `R` should be a root and we merge `L` and left son of `R`,
  186.       // and result is saved in `tmp`.
  187.       int tmp = merge(L, nodes_[R].left);
  188.       // `tmp` will be the new left son of `R`.
  189.       setParent(tmp, R);
  190.       nodes_[R].left = tmp;
  191.       fixSize(R);
  192.       return R;
  193.     } else {
  194.       // In this case `L` will be a root.
  195.       int tmp = merge(nodes_[L].right, R);
  196.       setParent(tmp, L);
  197.       nodes_[L].right = tmp;
  198.       fixSize(L);
  199.       return L;
  200.     }
  201.   }
  202.  
  203.   // Returns the index of `id`-th suffix (the suffix starting at position `id`)
  204.   // in the sorted array of all suffixes (empty suffix has index 0),
  205.   // the so-called order statistic of the suffix.
  206.   int getIndex(int id) {
  207.     // Zero node corresponds to empty suffix and has zero index.
  208.     if (!id) {
  209.       return 0;
  210.     }
  211.     // We add one more the size of its left subtree to the answer.
  212.     int index = nodes_[nodes_[id].left].size + 1;
  213.     while (nodes_[id].parent) {
  214.       int par = nodes_[id].parent;  // Ancestor of the initial node `id`
  215.       if (id == nodes_[par].right) {
  216.         // If node `id` is the right son of `par`,
  217.         // we add one more the size of left subtree of `par` to the answer as above.
  218.         index += nodes_[nodes_[par].left].size + 1;
  219.       }
  220.       id = par;
  221.     }
  222.     return index;
  223.   }
  224.  
  225.   // Returns result of comparison of i-th and j-th suffixes.
  226.   // Result is negative if i-th suffix smaller, positive if it's larger,
  227.   // and zero when they are equal (i.e. when i = j).
  228.   // It is not assumed these suffixes has correct positions in the tree,
  229.   // but (i-1)-th and (j-1)-th suffixes should have ones.
  230.   int compare(int i, int j) {
  231.     // At first we compare their first characters.
  232.     int cmp = str_[i] - str_[j];
  233.     if (cmp == 0)
  234.       // If they are different we compare order statistics
  235.       // for (i-1)-th and (j-1)-th suffixes.
  236.       cmp = getIndex(i - 1) - getIndex(j - 1);
  237.     return cmp;
  238.   }
  239.  
  240.   // Inserts node `id` to the subtree rooted at `tree`
  241.   // and returns the new root of this subtree (it may change).
  242.   int insert(int tree, int id) {
  243.     // In the case of empty subtree the node `id` will be a new root.
  244.     if (!tree) {
  245.       return id;
  246.     }
  247.     // The treap should be a heap by `y` fields.
  248.     // Hence if `id` has larger `y` than `tree`, `id` should be a new root.
  249.     if (nodes_[tree].y < nodes_[id].y) {
  250.       // In this case we split subtree rooted at `tree` into two parts:
  251.       // 1) with suffixes < the `id`-th suffix (the root is left son of `id`);
  252.       // 2) with suffixes > the `id`-th suffix (the root is right son of `id`).
  253.       split(tree, id, nodes_[id].left, nodes_[id].right);
  254.       // We set parents of both left and right sons if `id` to be `id`.
  255.       setParent(nodes_[id].left, id);
  256.       setParent(nodes_[id].right, id);
  257.       fixSize(id);
  258.       return id;  // This case is terminal for insert query.
  259.     }
  260.     // Otherwise we should move `id` to one of the subtrees of the node `tree`,
  261.     // selecting the correct subtree by comparing suffixes at `tree` and `id`.
  262.     int cmp = compare(id, tree);
  263.     if (cmp < 0) {
  264.       // If `id` is less than `tree` than we insert it to the left subtree.
  265.       // `tmp` is the root of this subtree after inserting.
  266.       int tmp = insert(nodes_[tree].left, id);
  267.       // And since root of this subtree could change,
  268.       // we fix relation between `tree` and `tmp`
  269.       setParent(tmp, tree);
  270.       nodes_[tree].left = tmp;
  271.     } else {
  272.       // Now cmp > 0 since all suffixes are different
  273.       // and we insert `id` to the right subtree.
  274.       int tmp = insert(nodes_[tree].right, id);
  275.       setParent(tmp, tree);
  276.       nodes_[tree].right = tmp;
  277.     }
  278.     // We should fix the field `size` of the node `tree`.
  279.     // We can simply increase it by 1 since we add only one node to its subtree.
  280.     nodes_[tree].size++;    
  281.     return tree;  // `tree` remains the root of its subtree
  282.   }
  283.  
  284.   // Splits the subtree rooted at `tree` by the node `id` into two parts:
  285.   // 1) with suffixes < the `id`-th suffix (the root is `L`);
  286.   // 2) with suffixes > the `id`-th suffix (the root is `R`).
  287.   // `id`-th node does not have to be a correct node of the tree.
  288.   // But node `id - 1` should be.
  289.   void split(int tree, int id, int& L, int& R) {
  290.     // In the case of empty subtree there is nothing to split,
  291.     // and both `L` and `R` should be empty trees as well.
  292.     if (!tree) {
  293.       L = R = 0;
  294.       return;
  295.     }
  296.     // Otherwise we compare the root of the subtree with the node `id`.
  297.     int cmp = compare(id, tree);
  298.     if (cmp < 0) {
  299.       // If `id` < `tree` then we should split left subtree of `tree` by `id`
  300.       // and place the second subtree to the root of left subtree itself,
  301.       split(nodes_[tree].left, id, L, nodes_[tree].left);
  302.       setParent(nodes_[tree].left, tree);
  303.       R = tree;
  304.     } else {
  305.       // Otherwise cmp > 0 and we split right subtree by the node `id`.
  306.       split(nodes_[tree].right, id, nodes_[tree].right, R);
  307.       setParent(nodes_[tree].right, tree);
  308.       L = tree;
  309.     }
  310.     fixSize(tree);
  311.   }
  312. };
  313.  
  314. // Returns the prefix function of the string s. Namely, pf[i]
  315. // is the length of longest proper prefix of s that is the suffix of s[0..i].
  316. // Classical Knuth-Morris-Pratt preprocessing with complexity O(|s|) is used.
  317. vector<int> prefixFunction(const string& s) {
  318.   int n = s.size();
  319.   vector<int> pf(n);
  320.   pf[0] = 0;
  321.   for (int i = 1; i < n; ++i) {
  322.     pf[i] = pf[i - 1];
  323.     while (pf[i] && s[i] != s[pf[i]]) {
  324.       pf[i] = pf[pf[i] - 1];
  325.     }
  326.     if (s[i] == s[pf[i]]) {
  327.       pf[i]++;
  328.     }
  329.   }
  330.   return pf;
  331. }
  332.  
  333. // Returns the number of occurrences of the string `q` in the string `s`.
  334. // `pf` should contain the computed prefix function of `q`.
  335. // Classical Knuth-Morris-Pratt algorithm with complexity O(|s|) is used.
  336. int match(const string& q, const vector<int>& pf, const string &s)
  337. {
  338.   int n = s.size();
  339.   int count = 0;
  340.   int pr = 0;
  341.   for (int i = 0; i < n; ++i) {
  342.     char c = s[i];
  343.     while (pr > 0 && q[pr] != c) {
  344.       pr = pf[pr - 1];
  345.     }
  346.     if (q[pr] == c) pr++;
  347.     if (pr == q.size()) {
  348.       count++;
  349.       pr = pf[pr - 1];
  350.     }
  351.   }
  352.   return count;
  353. }
  354.  
  355. // Returns the reverse of the string `s`
  356. string reverse(string s) {
  357.   reverse(s.begin(), s.end());
  358.   return s;
  359. }
  360.  
  361. // Supports the following types of queries on the string S:
  362. // - pushRight(c) - inserts character `c` to the end of the string.
  363. // - pushLeft(c)  - inserts character `c` to the beginning of the string.
  364. // - popRight()   - deletes the last character of S and returns its value.
  365. // - popLeft()    - deletes the first character of S and returns its value.
  366. // - size()       - returns the length of the string.
  367. // - at(i)        - returns the i-th character of S in 0-based numeration.
  368. // - match(q)     - returns the number of occurrences of the string `q` in S.
  369. // Occupies O(|S|) memory at each moment.
  370. class StringDeque {
  371.  private:
  372.   // At each moment `left_` contains some prefix A of S,
  373.   // while `right_` contains the remaining suffix B of S but in reversed order.
  374.   // Thus, S = A + B = left_ + reverse(right_)
  375.   DynamicSuffixArray left_;
  376.   DynamicSuffixArray right_;
  377.  
  378.  public:
  379.   StringDeque(const string& s) {
  380.     // For ease of code we simply push all characters to the `right_`,
  381.     // keeping `left_` empty.
  382.     for (int i = 0; i < s.size(); ++i) {
  383.       pushRight(s[i]);
  384.     }
  385.   }
  386.  
  387.   void pushRight(char c) {
  388.     right_.push(c);
  389.   }
  390.  
  391.   void pushLeft(char c) {
  392.     left_.push(c);
  393.   }
  394.  
  395.   char popRight() {
  396.     if (!right_.size()) {
  397.       // In this case we should pop the last character of `left_`, which
  398.       // is not supported. Hence in O(|S|) time we divide `left_` into
  399.       // nearly equal parts and assign reverse of the second part to `right_`.
  400.       equalize(right_, left_);
  401.     }
  402.     return right_.pop();
  403.   }
  404.  
  405.   char popLeft() {
  406.     if (!left_.size()) {
  407.       // Now `right_` contains S reversed. So we divide it into nearly
  408.       // equal parts, and assign the reverse of the second part to `left_`,
  409.       // which is exactly the prefix of S since `right_` contains S reversed.
  410.       equalize(left_, right_);
  411.     }
  412.     return left_.pop();
  413.   }
  414.  
  415.   int size() {
  416.     return left_.size() + right_.size();
  417.   }
  418.  
  419.   char at(int i) {
  420.     if (i < left_.size()) {
  421.       return left_.at(i);
  422.     }
  423.     // revat() is called since `right_` contains the reversed suffix of S.
  424.     return right_.revat(i - left_.size());
  425.   }
  426.  
  427.   // `pf` should be correctly computed prefix function of `q`
  428.   int match(const string& q, const vector<int>& pf) {
  429.     // `border` is a concatenation of last min(|A|, |q|-1) characters of A
  430.     // and first min(|B|, |q|-1) characters of B,
  431.     // where A and B are defined above.
  432.     string border = "";
  433.     for (int i = max(0, left_.size() - (int)q.size() + 1); i < left_.size(); ++i) {
  434.       border += left_.at(i);
  435.     }
  436.     for (int i = 0; i < (int)q.size() - 1 && i < right_.size(); ++i) {
  437.       // To access i-th character of B we should access i-th character
  438.       // of `right_` in reversed order, hence `revat()`.
  439.       border += right_.revat(i);
  440.     }
  441.     // Each occurrence of `q` in S is either in A, or in B or in `border`.
  442.     // And since `border` contains less than |q| characters from A and from B,
  443.     // this occurrences are different. Since `right_` contains reversed
  444.     // suffix of S we pass reversed `q` to right_.match().
  445.     return left_.match(q) + right_.match(reverse(q)) + ::match(q, pf, border);
  446.   }
  447.  
  448.  private:
  449.   // `a` contains empty string, `b` is not.
  450.   // `a` will contain last (|b|+1) div 2 characters of `b` in reversed order,
  451.   // while `b` will contain the last |b| div 2 its characters.
  452.   // So `a` will be non-empty after that.
  453.   void equalize(DynamicSuffixArray& a, DynamicSuffixArray& b) {
  454.     int n = b.size();
  455.     int m = n / 2;
  456.     for (int i = m; i < n; ++i) {
  457.       a.push(b.at(i));
  458.     }
  459.     // `tmp` will contain first `m` characters of `b` in reversed order.
  460.     string tmp = "";
  461.     for (int i = m - 1; i >= 0; --i) {
  462.       tmp += b.at(i);
  463.     }
  464.     // We clear `b` and push characters of `tmp` to `b`.
  465.     b = DynamicSuffixArray();  
  466.     for (int i = 0; i < m; ++i) {
  467.       b.push(tmp[i]);
  468.     }
  469.   }
  470. };
  471.  
  472. char buf[1500001];  // Needed to read strings fast using scanf.
  473.  
  474. // Reads the string `s` from stdin.
  475. void read(string& s) {
  476.   scanf("%s", buf);
  477.   s = buf;
  478. }
  479.  
  480. int main() {
  481.   string str0;  // Initial string.
  482.   read(str0);
  483.   int L = str0.size();
  484.   // `left` will always contain first (|S| div 2) characters of S,
  485.   // while `right` will contain the remaining characters of S.
  486.   // This is equivalent to |left| <= |right| <= |left| + 1.
  487.   StringDeque left(str0.substr(0,L/2));
  488.   StringDeque right(str0.substr(L/2));   
  489.   int Q;
  490.   scanf("%d", &Q);
  491.   for (int it = 0; it < Q; ++it) {
  492.     string op;  // The current operation.
  493.     read(op);
  494.     // In the case of insert operation we read the character we need to insert.
  495.     char c;
  496.     if(op.substr(0,6) == "INSERT") {
  497.       scanf(" %c", &c);
  498.     }
  499.     if (op == "INSERT_LEFT") {
  500.       left.pushLeft(c);
  501.     } else if (op == "INSERT_RIGHT") {
  502.       right.pushRight(c); 
  503.     } else if (op == "INSERT_MIDDLE") {
  504.       if(left.size() == right.size()) {
  505.         right.pushLeft(c);
  506.       } else {
  507.         left.pushRight(c);
  508.       }
  509.     } else if (op == "DELETE_LEFT") {
  510.       left.popLeft();
  511.     } else if (op == "DELETE_RIGHT") {
  512.       right.popRight();
  513.     } else if (op == "DELETE_MIDDLE") {
  514.       right.popLeft();
  515.     } else { // op == "QUERY"
  516.       string q;
  517.       read(q);
  518.       vector<int> pf = prefixFunction(q);
  519.       int L = q.size();
  520.       int L1 = left.size();
  521.       int L2 = right.size();
  522.       // `border` is a concatenation of suffix of `left` of length min(L1, L-1)
  523.       // and prefix of `right` of length min(L2, L-1)
  524.       string border = "";
  525.       for (int i = max(0, L1 - L + 1); i < L1; ++i) {
  526.         border += left.at(i);
  527.       }
  528.       for (int i = 0; i < L2 && i < L - 1; ++i) {
  529.         border += right.at(i);
  530.       }
  531.       // The number of occurrences of `q` is counted similarly as in StringDeque.
  532.       int count = left.match(q, pf) + right.match(q, pf) + match(q, pf, border);
  533.       printf("%d\n", count);
  534.     }
  535.     // After insert or delete queries condition |left| <= |right| <= |left| + 1
  536.     // could be broken, so we equalize `left` and `right` by additional
  537.     // movements of characters from one of them to another.
  538.     while (left.size() + 2 <= right.size()) {
  539.       left.pushRight(right.popLeft());
  540.     }
  541.     while (left.size() > right.size()) {
  542.       right.pushLeft(left.popRight());
  543.     }
  544.   }
  545.   return 0;
  546. }
  547.  
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yQVBU4
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 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!