fork download
copy 
  1. // ﷽
  2. // Contest: string (medium)
  3. //
  4. // Judge: Codeforces
  5. // URL: https://c...content-available-to-author-only...s.com/group/o09Gu2FpOx/contest/559867/problem/C
  6. // Memory Limit: 512
  7. // Time Limit: 10000
  8. // Start: Thu 08 May 2025 12:25:56 AM EEST
  9. #include <bits/stdc++.h>
  10.  
  11. #ifdef ALGOAT
  12. #include "debug.hpp"
  13. #else
  14. #define debug(...) 0
  15. #define debug_itr(...) 0
  16. #define debug_bits(...) 0
  17. #endif
  18.  
  19. // 48-57 -> 0-9  65-90 -> A-Z 97-122 -> a-z
  20. #define fastio()                                                               \
  21.   ios_base::sync_with_stdio(false);                                            \
  22.   cin.tie(NULL);
  23.  
  24. #define int long long
  25. #define F first
  26. #define S second
  27. #define all(a) (a).begin(), (a).end()
  28. #define rall(a) (a).rbegin(), (a).rend()
  29. #define rep(i, a, b) for (int i = (a); i < (b); ++i)
  30. #define sz(x) (int)(x).size()
  31. #define vi vector<int>
  32.  
  33. /*template <class T> using rpq = priority_queue<T, vector<T>, greater<T>>;*/
  34.  
  35. const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1},
  36.           dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
  37.  
  38. using namespace std;
  39.  
  40. struct AhoCorasick {
  41.   enum { alpha = 26, first = 'a' }; // change this!
  42.   struct Node {
  43.     // (nmatches is optional)
  44.     int back, next[alpha], start = -1, end = -1, nmatches = 0;
  45.     Node(int v) { memset(next, v, sizeof(next)); }
  46.   };
  47.   vector<Node> N;
  48.   vi backp;
  49.   void insert(string &s, int j) {
  50.     assert(!s.empty());
  51.     int n = 0;
  52.     for (char c : s) {
  53.       int &m = N[n].next[c - first];
  54.       if (m == -1) {
  55.         n = m = sz(N);
  56.         N.emplace_back(-1);
  57.       } else
  58.         n = m;
  59.     }
  60.     if (N[n].end == -1)
  61.       N[n].start = j;
  62.     backp.push_back(N[n].end);
  63.     N[n].end = j;
  64.     N[n].nmatches++;
  65.   }
  66.   AhoCorasick(vector<string> &pat) : N(1, -1) {
  67.     rep(i, 0, sz(pat)) insert(pat[i], i);
  68.     N[0].back = sz(N);
  69.     N.emplace_back(0);
  70.  
  71.     queue<int> q;
  72.     for (q.push(0); !q.empty(); q.pop()) {
  73.       int n = q.front(), prev = N[n].back;
  74.       rep(i, 0, alpha) {
  75.         int &ed = N[n].next[i], y = N[prev].next[i];
  76.         if (ed == -1)
  77.           ed = y;
  78.         else {
  79.           N[ed].back = y;
  80.           (N[ed].end == -1 ? N[ed].end : backp[N[ed].start]) = N[y].end;
  81.           N[ed].nmatches += N[y].nmatches;
  82.           q.push(ed);
  83.         }
  84.       }
  85.     }
  86.   }
  87.   vi find(string word) {
  88.     int n = 0;
  89.     vi res; // int count = 0;
  90.     for (char c : word) {
  91.       n = N[n].next[c - first];
  92.       res.push_back(N[n].end);
  93.       // count += N[n].nmatches;
  94.     }
  95.     return res;
  96.   }
  97.   vector<vi> findAll(vector<string> &pat, string word) {
  98.     vi r = find(word);
  99.     vector<vi> res(sz(word));
  100.     rep(i, 0, sz(word)) {
  101.       int ind = r[i];
  102.       while (ind != -1) {
  103.         res[i - sz(pat[ind]) + 1].push_back(ind);
  104.         ind = backp[ind];
  105.       }
  106.     }
  107.     return res;
  108.   }
  109. };
  110.  
  111. void solve() {
  112.   int n;
  113.   cin >> n;
  114.   vector<string> dict(n);
  115.   for (auto &x : dict)
  116.     cin >> x;
  117.   string s;
  118.   cin >> s;
  119.   int m = s.size();
  120.  
  121.   AhoCorasick ac(dict);
  122.   const int INF = INT_MAX / 2;
  123.   vector<int> dp(m + 1, INF);
  124.  
  125.   dp[0] = 0;
  126.  
  127.   int node = 0;
  128.   const int MOD = 1e9 + 7;
  129.   for (int i = 0; i < m; ++i) {
  130.     node = ac.N[node].next[s[i] - 'a'];
  131.     for (int out = ac.N[node].end; out != -1; out = ac.backp[out]) {
  132.       int len = dict[out].size();
  133.       dp[i + 1] = min(dp[i + 1] , dp[i + 1 - len]+1 );
  134.     }
  135.   }
  136.  
  137.   cout << (dp[m] >= INF ? -1 : dp[m]) << "\n";
  138.  
  139. }
  140.  
  141. int32_t main() {
  142.   /*freopen("whereami.in", "r", stdin);*/
  143.   /*freopen("whereami.out", "w", stdout);*/
  144.   fastio();
  145.   int n = 1;
  146.  
  147. #ifdef MUTLI_CASE
  148.   cin >> n;
  149. #endif
  150.   while (n--)
  151.     solve();
  152.   return 0;
  153. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/k15Hf5
Aho
language:
C++14 (gcc 8.3)
created:
3 days 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!