fork download
copy 
  1. // embrace the struggle
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #pragma optimize GCC("O3")
  6. #pragma optimize GCC("Ofast")
  7.  
  8. using namespace std;
  9. using ll = long long;
  10.  
  11. #define sz(st) int(st.size())
  12. #define all(st) st.begin(), st.end()
  13. const int N = 100 + 5;
  14. ll dp[N][N];
  15. vector<vector<string> > a;
  16. int n;
  17. string t;
  18.  
  19. bool check(int idx, const string &cur)
  20. {
  21.     int i = 0;
  22.     while (idx < sz(t) && i < sz(cur)) {
  23.         if (cur[i] == t[idx]) {
  24.             idx++, i++;
  25.         } else break;
  26.     }
  27.     return i == sz(cur);
  28. }
  29.  
  30. ll rec(int idx, int j)
  31. {
  32.     if (j == sz(t)) return 0;
  33.     if (idx == n) return 1e9;
  34.  
  35.     ll &ret = dp[idx][j];
  36.     if (ret != -1) return ret;
  37.     ret = rec(idx + 1, j);
  38.     int len = sz(t) - j;
  39.     for (const string &s: a[idx]) {
  40.         if (sz(s) > len) continue;
  41.         if (check(j, s)) {
  42.             ret = min(ret, 1 + rec(idx + 1, j + sz(s)));
  43.         }
  44.     }
  45.     return ret;
  46. }
  47.  
  48.  
  49. void Solve()
  50. {
  51.     cin >> t;
  52.     cin >> n;
  53.     a = vector<vector<string> >(n);
  54.     memset(dp, -1, sizeof(dp));
  55.  
  56.     for (int i = 0; i < n; i++) {
  57.         int m;
  58.         cin >> m;
  59.         string temp;
  60.         while (m--) {
  61.             cin >> temp;
  62.             a[i].push_back(temp);
  63.         }
  64.     }
  65.     ll ans = rec(0, 0);
  66.     if (ans == 1e9) cout << -1;
  67.     else cout << ans;
  68. }
  69.  
  70. signed main()
  71. {
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.     int t = 1;
  75.     //cin >> t;
  76.     for (int tc = 1; tc <= t; tc++) {
  77.         Solve();
  78.         cout << "\n";
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de
stdout
copy 
2
https://ideone.com/JHr0TE
language:
C++14 (gcc 8.3)
created:
19 hours 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!