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. vector<int>nxt[26];
  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 = lower_bound(nxt[a[i] - 'a'].begin(), nxt[a[i] - 'a'].end(), j) - nxt[a[i] - 'a'].begin();
  28. 	if (idx == nxt[a[i] - 'a'].size())
  29. 		ret = min(ret, calc(i + 1, m));
  30. 	else
  31. 		ret = min(ret, calc(i + 1, nxt[a[i] - 'a'][idx] + 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 = lower_bound(nxt[a[i] - 'a'].begin(), nxt[a[i] - 'a'].end(), j) - nxt[a[i] - 'a'].begin();
  41. 	if (idx == nxt[a[i] - 'a'].size() && best == 1){
  42. 		printf("%c\n", a[i]);
  43. 		return;
  44. 	}
  45. 	else if (best == calc(i + 1, nxt[a[i] - 'a'][idx] + 1) + 1){
  46. 		printf("%c", a[i]);
  47. 		print(i + 1, nxt[a[i] - 'a'][idx] + 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 < m; ++i)
  57. 		nxt[b[i] - 'a'].push_back(i);
  58. 	printf("%d\n", calc(0, 0));
  59. 	print(0, 0);
  60. }
Success #stdin #stdout 0s 7200KB
comments (?)
stdin 
babab
babba
stdout 
3
aab
https://ideone.com/bMBs68
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!