fork download
copy 
  1. // copied palindromic tree code from https://g...content-available-to-author-only...b.com/ADJA/algos/blob/master/Strings/PalindromeTree.cpp
  2.  
  3. /**************************************************************************************
  4.     Palindrome tree. Useful structure to deal with palindromes in strings. O(N)
  5.     This code counts number of palindrome substrings of the string.
  6.     Based on problem 1750 from informatics.mccme.ru:
  7.     http://i...content-available-to-author-only...e.ru/moodle/mod/statements/view.php?chapterid=1750
  8. **************************************************************************************/
  9.  
  10. #include <iostream>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <map>
  17. #include <string>
  18. #include <utility>
  19. #include <cstring>
  20. #include <cassert>
  21. #include <cmath>
  22. #include <stack>
  23. #include <queue>
  24.  
  25. using namespace std;
  26.  
  27.  
  28. const int MAXN = 1005000;
  29.  
  30. struct node {
  31.     int next[2];
  32.     int len;
  33.     int sufflink;
  34.     int quicklink;
  35.     int num;
  36. };
  37.  
  38. int len;
  39. int s[MAXN];
  40. node tree[MAXN]; 
  41. int num;            // node 1 - root with len -1, node 2 - root with len 0
  42. int suff;           // max suffix palindrome
  43.  
  44. bool addLetter(int pos) {
  45.     int cur = suff, curlen = 0;
  46.     int let = s[pos];
  47.  
  48.     while(true) {
  49.         curlen = tree[cur].len;
  50.         if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])     
  51.             break;
  52.         int tmpcur = cur;
  53.         cur = tree[cur].sufflink;
  54.  
  55.         curlen = tree[cur].len;
  56.         if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])     
  57.             break;
  58.         cur = tree[tmpcur].quicklink;
  59.     }
  60.     if (tree[cur].next[let]) {  
  61.         suff = tree[cur].next[let];
  62.         return false;
  63.     }
  64.  
  65.     num++;
  66.     suff = num;
  67.     tree[num].len = tree[cur].len + 2;
  68.     tree[cur].next[let] = num;
  69.  
  70.     if (tree[num].len == 1) {
  71.         tree[num].sufflink = 2;
  72.         tree[num].quicklink = 2;
  73.         return true;
  74.     }
  75.  
  76.     //puts(">>");
  77.     while (true) {
  78.         //printf("cur = %d -> %d, curlen = %d\n", cur, tree[cur].sufflink,curlen);
  79.         if(cur == 0 && curlen == 0) while(true);
  80.         cur = tree[cur].sufflink;
  81.         curlen = tree[cur].len;
  82.         if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
  83.             tree[num].sufflink = tree[cur].next[let];
  84.             break;
  85.         }       
  86.     }
  87.  
  88.     if(tree[num].sufflink > 0 && tree[tree[num].sufflink].sufflink > 0) {
  89.         if(s[pos - tree[tree[num].sufflink].len] == s[pos - tree[tree[tree[num].sufflink].sufflink].len]) {
  90.             tree[num].quicklink = tree[tree[num].sufflink].quicklink;
  91.         }else {
  92.             tree[num].quicklink = tree[tree[num].sufflink].sufflink;
  93.         }
  94.     }
  95.  
  96.     if(tree[num].quicklink == 0) {
  97.         tree[num].quicklink = tree[num].sufflink;
  98.     }
  99.  
  100.     return true;
  101. }
  102.  
  103. void initTree() {
  104.     suff = 2;
  105.     tree[1].len = -1; tree[1].sufflink = 1; tree[1].quicklink = 1;
  106.     tree[2].len = 0; tree[2].sufflink = 1; tree[2].quicklink = 1;
  107. }
  108.  
  109. int main() {
  110. #ifdef IN_MY_COMPUTER
  111.     freopen("example.in.txt", "r", stdin);
  112.     freopen("example.out.txt", "w", stdout);
  113. #endif
  114.     int Q; scanf("%d", &Q);
  115.  
  116.     num = 2;
  117.     initTree();
  118.  
  119.     std::stack<std::pair<int, int>> suffs;
  120.     suffs.emplace(0, 0);
  121.     for(int q = 0; q < Q; q++) {
  122.         int type; scanf("%d", &type);
  123.         if(type == 1) {
  124.             int c; scanf("%d" ,&c);
  125.             s[len++] = c;
  126.             addLetter(len-1);
  127.             suffs.emplace(suff, std::max(suffs.top().second, tree[suff].len));
  128.         }else {
  129.             len--;
  130.             suffs.pop();
  131.             suff = suffs.top().first;
  132.             if(len == 0) initTree();
  133.         }
  134.         printf("%d\n", suffs.top().second);
  135.     }
  136.  
  137.     return 0;
  138. }
Runtime error #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/21XLLs
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!