fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. #define maxn 300000
  8. #define limit 1000000000000000000LL
  9.  
  10. long long k;
  11.  
  12. int n, m, i, j, cur, bad_value, kk;
  13. char a[maxn], b[maxn];
  14. bool was[30];
  15. pair<int, int> srt[maxn * 2 + 3];
  16.  
  17. struct sfa {
  18.  
  19. 	long long dp[maxn * 2 + 3], grundy_sum[30], ways[maxn * 2 + 3];
  20.  
  21. 	int next[maxn * 2 + 3][26], len[maxn * 2 + 3], lnk[maxn * 2 + 3], grundy[maxn * 2 + 3];
  22. 	int nodes, last, j;
  23.  
  24. 	void init () {
  25. 		nodes = last = 1;
  26. 		len[1] = lnk[1] = 0;
  27. 	}
  28.  
  29. 	void push (int c) {
  30. 		int cur = ++nodes, p;
  31. 		len[cur] = len[last] + 1;
  32. 		for(p = last; p && !next[p][c]; p = lnk[p]) next[p][c] = cur;
  33. 		if (!p) lnk[cur] = 1; else {
  34. 			int q = next[p][c];
  35. 			if (len[p] + 1 == len[q]) lnk[cur] = q; else {
  36. 				int clone = ++nodes;
  37. 				len[clone] = len[p] + 1;
  38. 				for(int j = 0; j < 26; j++) next[clone][j] = next[q][j];
  39. 				lnk[clone] = lnk[q];
  40. 				for(; p && next[p][c] == q; p = lnk[p]) next[p][c] = clone;
  41. 				lnk[q] = lnk[cur] = clone;
  42. 			}
  43. 		}
  44. 		last = cur;
  45. 	}
  46.  
  47. 	void grundy_precalc () {
  48. 		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
  49. 		sort(srt + 1, srt + nodes + 1);
  50. 		for(i = 1; i <= nodes; i++) {
  51. 			int k = srt[nodes - i + 1].second;
  52. 			dp[k] = 1;
  53. 			for(j = 0; j < 30; j++) was[j] = 0;
  54. 			for(j = 0; j < 26; j++) if (next[k][j]) was[grundy[next[k][j]]] = true;
  55. 			for(j = 0; j < 30; j++) if (!was[j]) {
  56. 				grundy[k] = j;
  57. 				break;
  58. 			}
  59. 		}		
  60. 	}	
  61.  
  62. 	void substr_precalc () {
  63. 		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
  64. 		sort(srt + 1, srt + nodes + 1);
  65. 		for(i = 1; i <= nodes; i++) {
  66. 			int k = srt[nodes - i + 1].second;
  67. 			dp[k] = 1;
  68. 			for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]];
  69. 		}
  70. 		ways[1] = 1;
  71. 		for(i = 1; i <= nodes; i++) for(j = 0; j < 26; j++) if (next[srt[i].second][j]) ways[next[srt[i].second][j]] += ways[srt[i].second];
  72. 		for(i = 1; i <= nodes; i++) grundy_sum[grundy[i]] += ways[i];
  73. 	}
  74.  
  75. 	void dp_recalc (int bad_value) {
  76. 		for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i);
  77. 		sort(srt + 1, srt + nodes + 1);
  78. 		for(i = 1; i <= nodes; i++) {
  79. 			int k = srt[nodes - i + 1].second;
  80. 			dp[k] = grundy[k] != bad_value;
  81. 			for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]];
  82. 		}
  83. 	}
  84.  
  85. } sfa1, sfa2;
  86.  
  87. int main (int argc, char * const argv[]) {
  88. //	freopen("input.txt", "r", stdin);
  89. 	scanf("%d %d %lld\n", &n, &m, &k);
  90.  
  91. 	sfa1.init();
  92. 	sfa2.init();
  93.  
  94. 	for(i = 0; i < n; i++) {
  95. 		a[i] = getchar();
  96. 		while (a[i] < 'a' || a[i] > 'z') a[i] = getchar();
  97. 		sfa1.push(a[i] - 'a');
  98. 	}
  99. 	for(i = 0; i < m; i++) {
  100. 		b[i] = getchar();
  101. 		while (b[i] < 'a' || b[i] > 'z') b[i] = getchar();
  102. 		sfa2.push(b[i] - 'a');
  103. 	}
  104.  
  105. 	sfa1.grundy_precalc();
  106. 	for(i = 1; i <= sfa2.nodes; i++) was[i] = false;
  107. 	sfa2.grundy_precalc();
  108.  
  109. 	sfa2.substr_precalc();	
  110.  
  111. 	for(i = 1; i <= sfa1.nodes; i++) srt[i] = make_pair(sfa1.len[i], i);
  112. 	sort(srt + 1, srt + sfa1.nodes + 1);
  113. 	for(i = 1; i <= sfa1.nodes; i++) {
  114. 		kk = srt[sfa1.nodes - i + 1].second;
  115. 		sfa1.dp[kk] = sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[kk]];
  116. 		for(j = 0; j < 26; j++) if (sfa1.next[kk][j]) {
  117. 			sfa1.dp[kk] += sfa1.dp[sfa1.next[kk][j]];
  118. 			if (sfa1.dp[kk] > limit) sfa1.dp[kk] = limit;
  119. 		}
  120. 	}		
  121.  
  122. 	if (k > sfa1.dp[1]) {
  123. 		puts("no solution");
  124. 		return 0;
  125. 	}
  126.  
  127. 	cur = 1;
  128. 	while (k > 0) {
  129. 		if (k <= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]]) break; else k -= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]];
  130. 		for(j = 0; j < 26; j++) if (k > sfa1.dp[sfa1.next[cur][j]]) k -= sfa1.dp[sfa1.next[cur][j]]; else {
  131. 			putchar('a' + j);
  132. 			cur = sfa1.next[cur][j];
  133. 			break;
  134. 		}
  135. 	}
  136. 	puts("");	
  137.  
  138. 	sfa2.dp_recalc(bad_value = sfa1.grundy[cur]);
  139. 	cur = 1;
  140. 	while (k > 0) {
  141. 		if (sfa2.grundy[cur] != bad_value) {
  142. 			--k;
  143. 			if (k == 0) break;
  144. 		}
  145. 		for(j = 0; j < 26; j++) if (k > sfa2.dp[sfa2.next[cur][j]]) k -= sfa2.dp[sfa2.next[cur][j]]; else {
  146. 			putchar('a' + j);
  147. 			cur = sfa2.next[cur][j];
  148. 			break;
  149. 		}
  150. 	}
  151. 	puts("");
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0s 162688KB
comments (?)
stdin
copy 
10 10 1287
jagsjdhgkj
dfsdfjhghs
stdout
copy 
s
fs
https://ideone.com/FPUPUo
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 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!