fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8SCk0x
language:
C++14 (gcc 8.3)
created:
8 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!