fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <string>
  10. #include <cstring>
  11. #include <cassert>
  12. #define rf freopen("in.in", "r", stdin)
  13. #define wf freopen("out.out", "w", stdout)
  14. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  15. using namespace std;
  16. const int mx = 1e5 + 10, mod = 1e9+7;
  17.  
  18. char S1[1111], S2[1111];
  19. int D[1111][1111], L[1111][1111];
  20. int pointer_S1[1111][26], pointer_S2[1111][26];
  21. int n, k;
  22.  
  23. void Calc_LCS_Number()
  24. {
  25. 	for(int i = n; i; --i)
  26. 	{
  27. 		for(int j = n; j; --j)
  28. 		{
  29. 			if(S1[i-1] == S2[j-1])
  30. 			{
  31. 				L[i][j] = L[i+1][j+1] + 1;
  32. 				D[i][j] = D[i+1][j+1];
  33. 			}
  34. 			else
  35. 			{
  36. 				L[i][j] = max(L[i+1][j], L[i][j+1]);
  37.  
  38. 				if(L[i+1][j] == L[i][j])
  39. 					D[i][j] = D[i][j] + D[i+1][j];
  40.  
  41. 				if(L[i][j+1] == L[i][j])
  42. 					D[i][j] = D[i][j] + D[i][j+1];
  43.  
  44. 				if(L[i][j] == L[i+1][j+1])
  45. 					D[i][j] -= D[i+1][j+1];
  46.  
  47. 				if(D[i][j] >= mod)
  48. 					D[i][j] = mod;
  49. 			}
  50. 		}
  51. 	}
  52. }
  53.  
  54. void pre_process()
  55. {
  56. 	memset(pointer_S1, -1, sizeof pointer_S1);
  57. 	memset(pointer_S2, -1, sizeof pointer_S2);
  58.  
  59. 	for(int i = n; i>=0; --i)
  60. 	{
  61. 		for(int j = 0; j<26; ++j)
  62. 		{
  63. 			if(pointer_S1[i][j] == -1)
  64. 				pointer_S1[i][j] = pointer_S1[i+1][j];
  65. 			if(pointer_S2[i][j] == -1)
  66. 				pointer_S2[i][j] = pointer_S2[i+1][j];
  67. 		}
  68.  
  69. 		if(i)
  70. 			pointer_S1[i-1][S1[i-1]-'a'] = i,
  71. 			pointer_S2[i-1][S2[i-1]-'a'] = i;
  72. 	}
  73. }
  74.  
  75. string final_process()
  76. {
  77. 	string ret = "";
  78. 	int idx_S1 = 0, idx_S2 = 0;
  79. 	L[0][0] = L[1][1] + 1;
  80. 	int cnt = 0;
  81.  
  82. 	while(L[idx_S1][idx_S2] > 1)
  83. 	{
  84. 		int count = 0, new_count = 0;
  85.  
  86. 		for(int letter = 0; letter<26; ++letter)
  87. 		{
  88. 			int tmp_S1 = pointer_S1[idx_S1][letter];
  89. 			int tmp_S2 = pointer_S2[idx_S2][letter];
  90.  
  91. 			if(tmp_S1 == -1 || tmp_S2 == -1)
  92. 				continue;
  93. 			if(L[idx_S1][idx_S2] != L[tmp_S1][tmp_S2]+1)
  94. 				continue;
  95.  
  96. 			new_count = count + D[tmp_S1][tmp_S2];
  97. 			if(new_count >= mod)
  98. 				new_count = mod;
  99.  
  100. 			if(count < k && k <= new_count)
  101. 			{
  102. 				k-=count;
  103. 				ret += (char)('a' + letter);
  104. 				idx_S1 = tmp_S1;
  105. 				idx_S2 = tmp_S2;
  106. 				break;
  107. 			}
  108.  
  109. 			count = new_count;
  110. 		}
  111. 	}
  112.  
  113. 	return ret;
  114. }
  115.  
  116. int main()
  117. {
  118. 	//rf;// wf;
  119. 	ios::sync_with_stdio(0);
  120.  
  121. 	cin >> n >> k;
  122. 	cin >> S1 >> S2;
  123. 	pre_process();
  124.  
  125. 	for(int i = 1; i<=n+1; ++i)
  126. 		D[n+1][i] = D[i][n+1] = 1;
  127.  
  128. 	Calc_LCS_Number();
  129. 	if(D[1][1] < k)
  130. 		printf("-1\n");
  131. 	else
  132. 		cout << final_process() << '\n';
  133.  
  134. 	return 0;
  135. }
Success #stdin #stdout 0s 13328KB
comments (?)
stdin
copy 
3 3
abc
cba
stdout
copy 
c
https://ideone.com/4t8D00
language:
C++ (gcc 8.3)
created:
8 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!