fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const ll Mod1 = 1000000007LL;
  8. const ll Mod2 = 1000000009LL;
  9. const ll Base = 271LL;
  10.  
  11. struct hashed_string{
  12.     vector <ll> prefix1, prefix2;
  13.     vector <ll> pow1, pow2;
  14.     ll n;
  15.  
  16.     hashed_string(string s){
  17.         n = s.size();
  18.         prefix1.assign(n, 0);
  19.         prefix2.assign(n, 0);
  20.         pow1.assign(n + 1, 0);
  21.         pow2.assign(n + 1, 0);
  22.  
  23.         pow1[0] = 1;
  24.         pow2[0] = 1;
  25.  
  26.         for (int i = 1; i <= n; i++){
  27.             pow1[i] = pow1[i - 1] * Base % Mod1;
  28.             pow2[i] = pow2[i - 1] * Base % Mod2;
  29.         }
  30.  
  31.         for (int i = 0; i < n; i++){
  32.             ll val = s[i] - 'a' + 1;
  33.  
  34.             prefix1[i] = ((i ? prefix1[i - 1] * Base : 0) + val) % Mod1;
  35.             prefix2[i] = ((i ? prefix2[i - 1] * Base : 0) + val) % Mod2;
  36.         }
  37.     }
  38.  
  39.     pair<ll,ll> get_hash(ll l, ll r){
  40.         ll h1 = prefix1[r];
  41.         ll h2 = prefix2[r];
  42.  
  43.         if (l >= 1){
  44.             h1 = (h1 - prefix1[l - 1] * pow1[r - l + 1] % Mod1 + Mod1) % Mod1;
  45.             h2 = (h2 - prefix2[l - 1] * pow2[r - l + 1] % Mod2 + Mod2) % Mod2;
  46.         }
  47.  
  48.         return {h1, h2};
  49.     }
  50. };
  51. void solve() {
  52.     ll n,m,x; string s1,s2;
  53.     cin >> n >> s1 >> m >> s2 >> x;
  54.     hashed_string v = hashed_string(s1);
  55.     hashed_string g = hashed_string(s2);
  56.     vector <vector <ll>> dp(n+1, vector <ll>(x+1, -1));
  57.     for (int i = 0; i <= n; i++){
  58.         for (int j = x; j >= 0; j--){
  59.             if (i >= 1)
  60.                 dp[i][j] = max(dp[i][j], dp[i-1][j]);
  61.             if (dp[i][j] == m - 1 || i == n || j == x) continue;
  62.             ll lo = dp[i][j] + 1;
  63.             ll hi = min(m - 1, dp[i][j] + n - i);
  64.             while (lo < hi){
  65.                 ll mid = (lo + hi + 1) / 2;
  66.                 if (g.get_hash(dp[i][j] + 1, mid) == v.get_hash(i, i + mid - dp[i][j] - 1)){
  67.                     lo = mid;
  68.                 }
  69.                 else{
  70.                     hi = mid - 1;
  71.                 }
  72.             }
  73.             if (g.get_hash(dp[i][j] +1, lo) == v.get_hash(i, i + lo - dp[i][j] - 1)){
  74.                 dp[i + lo - dp[i][j]][j + 1] = max(dp[i + lo - dp[i][j]][j + 1], lo);
  75.             }
  76.         }
  77.     }
  78.     ll answ = -1;
  79.     for (int i = 0; i <= x; i++){
  80.         answ = max(answ, dp[n][i]);
  81.     }
  82.     cout << (answ == m - 1 ? "YES" : "NO") << "\n";
  83. }
  84.  
  85. int main() {
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.  
  89.     ll t = 1;
  90.     while (t--) {
  91.         solve();
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/CaNVc6
language:
C++14 (clang 8.0)
created:
1 hour 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!