fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e6 + 42;
  6. map<char, int> to[maxn];
  7. int len[maxn], link[maxn], cnt[maxn];
  8. int last, sz = 1;
  9.  
  10. void add_letter(int &last, char c)
  11. {
  12. int p = last;
  13. if(to[p][c])
  14. {
  15. int q = to[p][c];
  16. if(len[q] == len[p] + 1)
  17. {
  18. last = q;
  19. return;
  20. }
  21. int cl = sz++;
  22. to[cl] = to[q];
  23. link[cl] = link[q];
  24. len[cl] = len[p] + 1;
  25. link[q] = last = cl;
  26. for(; to[p][c] == q; p = link[p])
  27. to[p][c] = cl;
  28. return;
  29. }
  30. last = sz++;
  31. len[last] = len[p] + 1;
  32. for(; to[p][c] == 0; p = link[p])
  33. to[p][c] = last;
  34. if(to[p][c] == last)
  35. return;
  36. int q = to[p][c];
  37. if(len[q] == len[p] + 1)
  38. {
  39. link[last] = q;
  40. return;
  41. }
  42. int cl = sz++;
  43. to[cl] = to[q];
  44. link[cl] = link[q];
  45. len[cl] = len[p] + 1;
  46. link[last] = link[q] = cl;
  47. for(; to[p][c] == q; p = link[p])
  48. to[p][c] = cl;
  49. }
  50.  
  51. int main()
  52. {
  53. int last = 0;
  54. for(int i = 0; i < 1e5; i++)
  55. add_letter(last, 'a');
  56. for(int i = last; i >= 0; i--)
  57. add_letter(i, 'b');
  58. }
  59.  
Time limit exceeded #stdin #stdout 5s 44824KB
stdin
Standard input is empty
stdout
Standard output is empty