fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. using namespace std;
  4. #define max(a,b) (a>b?a:b)
  5. const int MN = 250500;
  6. const int maxState = (MN << 1);
  7. struct State {
  8. 	State *go[26], *suffix;
  9. 	int depth, id;
  10. 	long long cnt;
  11. };
  12. State pool[maxState], *point, *root, *sink;
  13. int size;
  14. State *newState(int dep) {
  15. 	point->id = size++;
  16. 	point->depth = dep;
  17. 	return point++;
  18. }
  19. void init() {
  20. 	point = pool;
  21. 	size = 0;
  22. 	root = sink = newState(0);
  23. }
  24. void insert(int a) {
  25. 	State *p = newState(sink->depth+1);
  26. 	State *cur = sink, *sufState;
  27. 	while (cur && !cur->go[a]) {
  28. 		cur->go[a] = p;
  29. 		cur = cur->suffix;
  30. 	}
  31. 	if (!cur)
  32. 		sufState = root;
  33. 	else {
  34. 		State *q = cur->go[a];
  35. 		if (q->depth == cur->depth + 1)
  36. 			sufState = q;
  37. 		else {
  38. 			State *r = newState(cur->depth+1);
  39. 			memcpy(r->go, q->go, sizeof(q->go));
  40. 			r->suffix = q->suffix;
  41. 			q->suffix = r;
  42. 			sufState = r;
  43. 			while (cur && cur->go[a] == q) {
  44. 				cur->go[a] = r;
  45. 				cur = cur->suffix;
  46. 			}
  47. 		}
  48. 	}
  49. 	p->suffix = sufState;
  50. 	sink = p;
  51. }
  52. void solve(char buf[]) {
  53. 	int len = strlen(buf);
  54. 	int tmp = 0, ans = 0, anspos = 0;
  55. 	State *cur = root;
  56. 	for (int i = 0; i < len; i++) {
  57. 		if (cur->go[buf[i]-'a']) {
  58. 			tmp++;
  59. 			cur = cur->go[buf[i]-'a'];
  60. 		} else {
  61. 			while (cur && !cur->go[buf[i]-'a'])
  62. 				cur = cur->suffix;
  63. 			if (!cur) {
  64. 				cur = root;
  65. 				tmp = 0;
  66. 			} else {
  67. 				tmp = cur->depth + 1;
  68. 				cur = cur->go[buf[i]-'a'];
  69. 			}
  70. 		}
  71. 		if (ans < tmp) ans = tmp, anspos = i-tmp+1;
  72. 	}
  73. 	printf("%d\n",ans);
  74. 	for (int i = anspos; i <= anspos+ans-1; i++) printf("%c",buf[i]);
  75. }
  76. char ch[MN];
  77. int main() {
  78. 	scanf("%s", ch);
  79. 	init();
  80. 	int len = strlen(ch);
  81. 	for (int i = 0; i < len; i++) insert(ch[i]-'a');
  82. 	scanf("%s", ch);
  83. 	solve(ch);
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 64216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WEaTZK
language:
C++ (gcc 8.3)
created:
9 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!