fork(5) download
copy 
  1. //venk13
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <algorithm>
  8. #include <utility>
  9. #include <sstream>
  10. #include <iostream>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <ctime>
  15. #include <cstring>
  16. #include <fstream>
  17. #include <cassert>
  18.  
  19. using namespace std;
  20.  
  21. #define sz(a) (int)(a.size())
  22. #define len(a) (int)(a.length())
  23. #define pb push_back
  24. #define mp make_pair
  25.  
  26. ///////////////////////////http://c...content-available-to-author-only...s.com/blog/entry/4025
  27. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  28. const int MAXN = 1 << 19;
  29. string S;
  30. int N, gap;
  31. int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];
  32. bool sufCmp(int i, int j)
  33. {
  34. 	if (pos[i] != pos[j])
  35. 		return pos[i] < pos[j];
  36. 	i += gap;
  37. 	j += gap;
  38. 	return (i < N && j < N) ? pos[i] < pos[j] : i > j;
  39. }
  40. void buildSA()
  41. {
  42. 	N = len(S);
  43. 	REP(i, N) sa[i] = i, pos[i] = S[i];
  44. 	for (gap = 1;; gap *= 2)
  45. 	{
  46. 		sort(sa, sa + N, sufCmp);
  47. 		REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
  48. 		REP(i, N) pos[sa[i]] = tmp[i];
  49. 		if (tmp[N - 1] == N - 1) break;
  50. 	}
  51. }
  52. void buildLCP()
  53. {
  54. 	for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
  55. 	{
  56. 		for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
  57. 		++k;
  58. 		lcp[pos[i]] = k;
  59. 		if(k) --k;
  60. 	}
  61. }
  62. ///////////////////////////////
  63.  
  64. int main() {
  65. 	string A, B; cin >> A >> B;
  66. 	S = A + "$" + B + "#";
  67. 	buildSA(); buildLCP();
  68. 	int c2 = 1 << 30, maxFound = 0;
  69. 	for(int i = 0; i < len(S) - 1;) {
  70. 		int ptr = i, nwc1 = -1, nwc2 = 1 << 30, nowMax = lcp[i];
  71. 		while(ptr < len(S) - 1 && lcp[ptr] == nowMax) {
  72. 			if(sa[ptr] >= len(A)) nwc2 = min(nwc2, sa[ptr]);
  73. 			if(sa[ptr + 1] >= len(A)) nwc2 = min(nwc2, sa[ptr + 1]);
  74. 			if(sa[ptr] < len(A)) nwc1 = sa[ptr];
  75. 			if(sa[ptr + 1] < len(A)) nwc1 = sa[ptr + 1];
  76. 			ptr++;
  77. 		}
  78. 		if(nwc1 >= 0 && nwc2 < (1 << 30)) maxFound = max(maxFound, nowMax);
  79. 		i = ptr;
  80. 	}
  81. 	for(int i = 0; i < len(S) - 1;) {
  82. 		if(lcp[i] != maxFound) {
  83. 			i++;
  84. 			continue;
  85. 		}
  86. 		int ptr = i, nwc1 = -1, nwc2 = 1 << 30;
  87. 		while(ptr < len(S) - 1 && lcp[ptr] == maxFound) {
  88. 			if(sa[ptr] >= len(A)) nwc2 = min(nwc2, sa[ptr]);
  89. 			if(sa[ptr + 1] >= len(A)) nwc2 = min(nwc2, sa[ptr + 1]);
  90. 			if(sa[ptr] < len(A)) nwc1 = sa[ptr];
  91. 			if(sa[ptr + 1] < len(A)) nwc1 = sa[ptr + 1];
  92. 			ptr++;
  93. 		}
  94. 		if(nwc1 >= 0) c2 = min(c2, nwc2);
  95. 		i = ptr;
  96. 	}
  97. 	if(maxFound == 0) {
  98. 		cout << 0;
  99. 	}
  100. 	else {
  101. 		cout << S.substr(c2, maxFound) << '\n' << maxFound << '\n';
  102. 	}
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 11632KB
comments (?)
stdin
copy 
babaazzzzyy 
badyybac
stdout
copy 
ba
2
https://ideone.com/wct7zH
language:
C++ (gcc 8.3)
created:
10 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!