fork(1) download 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<memory.h>
  6. #include<stdio.h>
  7. #include<bitset>
  8. #include<vector>
  9. #include<set>
  10. #include<time.h>
  11. using namespace std;
  12. typedef long long ll;
  13. const int N = 1002;
  14. char a[N], b[N];
  15. int dp[N][N];
  16. int n, m;
  17. int nxt[26][N];
  18. int oo = 1e6;
  19. int calc(int i, int j){
  20. 	if (i == n)
  21. 		return oo;
  22. 	if (j == m)
  23. 		return 1;
  24. 	if (dp[i][j] != -1)
  25. 		return dp[i][j];
  26. 	int ret = calc(i + 1, j);
  27. 	int idx = nxt[a[i] - 'a'][j];
  28. 	if (idx == -1)
  29. 		ret = min(ret, calc(i + 1, m));
  30. 	else
  31. 		ret = min(ret, calc(i + 1, nxt[a[i] - 'a'][j] + 1) + 1);
  32. 	return dp[i][j] = ret;
  33. }
  34. void print(int i, int j){
  35. 	if (j == m){
  36. 		printf("%c\n", a[i]);
  37. 		return;
  38. 	}
  39. 	int best = calc(i, j);
  40. 	int idx = nxt[a[i] - 'a'][j];
  41. 	if (idx == -1 && best == 1){
  42. 		printf("%c\n", a[i]);
  43. 		return;
  44. 	}
  45. 	else if (best == calc(i + 1, nxt[a[i] - 'a'][j] + 1) + 1){
  46. 		printf("%c", a[i]);
  47. 		print(i + 1, nxt[a[i] - 'a'][j] + 1);
  48. 	}
  49. 	else print(i + 1, j);
  50. }
  51. int main(){
  52. 	memset(dp, -1, sizeof(dp));
  53. 	scanf("%s%s", &a, &b);
  54. 	n = strlen(a);
  55. 	m = strlen(b);
  56. 	for (int i = 0; i < 26; ++i)
  57. 		nxt[i][m - 1] = -1;
  58. 	nxt[b[m - 1] - 'a'][m - 1] = m - 1;
  59. 	for (int i = m - 2; i >= 0; --i){
  60. 		for (int j = 0; j < 26; ++j)
  61. 			nxt[j][i] = nxt[j][i + 1];
  62. 		nxt[b[i] - 'a'][i] = i;
  63. 	}
  64. 	printf("%d\n", calc(0, 0));
  65. 	print(0, 0);
  66. }
Success #stdin #stdout 0s 7168KB
comments (?)
stdin 
babab
babba
stdout 
3
aab
https://ideone.com/chXExW
language:
C++14 (gcc 8.3)
created:
9 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!