fork download
copy 
  1. // #define ONLINE_JUDGE
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #if !defined(mhnd01s) || defined(ONLINE_JUDGE)
  5. #define print(...) ((void)0)
  6. #endif
  7. using ll = long long;
  8. void solve();
  9. signed main() {
  10. #ifdef mhnd01s
  11.     int x = mt19937(random_device()())()%100;printf("%d\n", x);
  12.     freopen("out", "wt", stdout);
  13. #else
  14.     cin.tie(0)->sync_with_stdio(0);
  15. #endif
  16.     cin.exceptions(cin.failbit);
  17.     int t = 1;
  18.     cin >> t;
  19.     while(t--) {
  20.         solve();
  21.         if(t) cout << '\n';
  22.     }return 0;
  23. }
  24.  
  25. // fast hash
  26. using u64 = uint64_t;
  27. mt19937_64 rng = []{
  28.     uint64_t time_entropy = chrono::steady_clock::now().time_since_epoch().count();
  29.     uint64_t memory_entropy = (uintptr_t)make_unique<char>().get();
  30.     seed_seq ss{time_entropy, memory_entropy};
  31.     return mt19937_64(ss);
  32. }();
  33. struct hash61 {
  34.     static const uint64_t md = (1LL << 61) - 1;
  35.     static uint64_t step;
  36.     static vector<uint64_t> pw;
  37.     uint64_t addmod(uint64_t a, uint64_t b) const {
  38.         a += b;
  39.         if (a >= md) a -= md;
  40.         return a;
  41.     }
  42.  
  43.     uint64_t submod(uint64_t a, uint64_t b) const {
  44.         a += md - b;
  45.         if (a >= md) a -= md;
  46.         return a;
  47.     }
  48.  
  49.     uint64_t mulmod(uint64_t a, uint64_t b) const {
  50.         uint64_t l1 = (uint32_t) a, h1 = a >> 32, l2 = (uint32_t) b, h2 = b >> 32;
  51.         uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
  52.         uint64_t ret = (l & md) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  53.         ret = (ret & md) + (ret >> 61);
  54.         ret = (ret & md) + (ret >> 61);
  55.         return ret - 1;
  56.     }
  57.  
  58.     void ensure_pw(int sz) const {
  59.         int cur = (int) pw.size();
  60.         if (cur < sz) {
  61.             pw.resize(sz);
  62.             for (int i = cur; i < sz; i++) {
  63.                 pw[i] = mulmod(pw[i - 1], step);
  64.             }
  65.         }
  66.     }
  67.  
  68.     vector<uint64_t> pref, suff;
  69.     int n;
  70.  
  71.     template<typename T>
  72.     hash61(const T& s) {
  73.         n = (int) s.size();
  74.         ensure_pw(n + 1);
  75.         pref.resize(n + 1);
  76.         suff.resize(n + 1);
  77.         pref[0] = suff[n] = 1;
  78.         for (int i = 0; i < n; i++) {
  79.             pref[i + 1] = addmod(mulmod(pref[i], step), s[i]);
  80.         }
  81.         for (int i = n - 1; i >= 0; i--) {
  82.             suff[i] = addmod(mulmod(suff[i + 1], step), s[i]);
  83.         }
  84.     }
  85.  
  86.     uint64_t operator()(const int from, const int to) const {
  87.         assert(0 <= from && from <= to && to <= n - 1);
  88.         return submod(pref[to + 1], mulmod(pref[from], pw[to - from + 1]));
  89.     }
  90.  
  91.     uint64_t rev(const int from, const int to) const {
  92.         assert(0 <= from && from <= to && to <= n - 1);
  93.         return submod(suff[from], mulmod(suff[to + 1], pw[to - from + 1]));
  94.     }
  95. };
  96. uint64_t hash61::step = (md >> 2) + rng() % (md >> 1);
  97. vector<uint64_t> hash61::pw = vector<uint64_t>(1, 1);
  98.  
  99. void solve() {
  100.     int n, m;
  101.     string s, t; cin >> n >> m >> s >> t;
  102.  
  103.     if (s.size() < t.size()) return void(cout << -1);
  104.     if (s.size() == t.size())
  105.         return void(cout << (s == t ? 0 : -1));
  106.  
  107.     // dp[j][i] => 1 + min(dp[k+1][i+k-st+1]) for all matching strings
  108.  
  109.     vector<vector<int>> dp(m+1, vector<int>(n+1, -1));
  110.  
  111.     // hash, vector of starting points in s for that substring hash
  112.     map<u64, vector<int>> mp; 
  113.     hash61 hs(s), ht(t);
  114.     for (int sz = 1; sz <= m; sz++)
  115.         for (int i = 0; i+sz <= n; i++)
  116.             mp[hs(i, i+sz-1)].push_back(i);
  117.  
  118.     function<int(int, int)> rec = [&](int j, int i) -> int {
  119.         if (j == m) return i < n; // end of t: check if some characters left in s
  120.         if (i == n) return 100000000; // end of s before end of t: invalid
  121.  
  122.         int& ret = dp[j][i];
  123.         if (~ret) return ret;
  124.         ret = 1e8;
  125.  
  126.         for (int k = j; k < m; k++)
  127.             for (int st : mp[ht(j, k)]) { // substring in t matches some starting points in s
  128.             	if (st < i) continue;
  129.                 int sz = k-j+1;
  130.                 int nst = st+sz;
  131.                 int ost = i+sz;
  132.                 // if i skipped some characters in s after matching with t
  133.                 ret = min(ret, bool(nst ^ ost) + rec(k+1, nst)); 
  134.             }
  135.  
  136.         return ret;
  137.     };
  138.  
  139.     cout << (rec(0, 0) > n ? -1 : dp[0][0]);
  140. }
  141.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5
3 2
abc
ac
2 2
ab
ba
4 4
abcd
abcd
5 2
ababa
ba
5 2
ababa
bb
stdout
copy 
1
-1
0
1
3
https://ideone.com/6Ws1iP
language:
C++14 (gcc 8.3)
created:
1 day 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!