fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
  6. #define        FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
  7. #define       FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
  8. #define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  9.  
  10. template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
  11.  
  12. // end of template
  13.  
  14. const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
  15. const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
  16. const int MAX_S = 1e4 + 4;
  17. const int MAX_T = 1e3 + 3;
  18.  
  19. string S, T;
  20. int kmp[MAX_T], nxt[MAX_T][256], szT, szS;
  21.  
  22. void init(void) {
  23. 	cin >> S >> T;
  24. 	szS = S.size(); szT = T.size();
  25. 	S = ' ' + S + ' '; T = ' ' + T + ' ';
  26. 	REP(j, 26) nxt[0][j] = 0;
  27. 	kmp[0] = 0; nxt[0][T[1] - 'a'] = 1;
  28. 	FOR(i, 1, szT) {
  29. 		kmp[i] = i == 1 ? 0 : nxt[kmp[i - 1]][T[i] - 'a'];
  30. 		REP(j, 26) nxt[i][j] = j == T[i + 1] - 'a' ? i + 1 : nxt[kmp[i]][j];
  31. 	}
  32. }
  33.  
  34. int dp[MAX_S][MAX_T];
  35.  
  36. void process(void) {
  37. 	memset(dp, 0x3f, sizeof(dp));
  38. 	dp[0][0] = 0;
  39. 	REP(i, szS) REP(j, szT) {
  40. 		minimize(dp[i + 1][nxt[j][S[i + 1] - 'a']], dp[i][j]);
  41. 		minimize(dp[i + 1][j], dp[i][j] + 1);
  42. 	}
  43. 	int res = szS;
  44. 	REP(j, szT) minimize(res, dp[szS][j]);
  45. 	cout << res << '\n';
  46. }
  47.  
  48. int main(void) {
  49. 	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
  50. 	file("pstring");
  51. 	REP(love, 3) {
  52. 		init();
  53. 		process();
  54. 	}
  55. 	return (0^0);
  56. }
Runtime error #stdin #stdout 0.01s 42640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RIt3QJ
language:
C++14 (gcc 8.3)
created:
1 year 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!