test/misc/joisc2010_dna.test.cpp

• View this file on GitHub
• Last update: 2025-08-12 18:50:34+09:00
• Problem: https://www2.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf#2

Depends on

• Aho-Corasick (src/String/AhoCorasick.hpp)

Code

// competitive-verifier: PROBLEM https://www2.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf#2
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64

#include <iostream>
#include "src/String/AhoCorasick.hpp"
using namespace std;
int main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 int N;
 cin >> N;
 string S;
 cin >> S;
 int M= S.length();
 vector<string> t(N);
 for (int i= 0; i < N; i++) cin >> t[i];
 AhoCorasick ac(t);
 vector<int> dp(M + 1, 1 << 30);
 dp[0]= 0;
 for (int i= 0, s= ac.initial_state();;) {
  auto ps= ac.matched_patterns(s);
  for (int j: ps) {
   int l= t[j].length();
   if (l == i) dp[i]= 1;
   for (int k= i - 1; k >= 0 && k > i - l; k--) {
    dp[i]= min(dp[i], dp[k] + 1);
   }
  }
  if (i == M) break;
  s= ac.transition(s, S[i++]);
 }
 cout << dp[M] << '\n';
 return 0;
}

#line 1 "test/misc/joisc2010_dna.test.cpp"
// competitive-verifier: PROBLEM https://www2.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf#2
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64

#include <iostream>
#line 2 "src/String/AhoCorasick.hpp"
#include <vector>
#include <algorithm>
#include <numeric>
template <class String> struct AhoCorasick {
 using symbol_t= typename String::value_type;
 AhoCorasick(const std::vector<String> &ps) {
  const size_t n= ps.size();
  std::vector<int> ord(n), rows;
  std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int l, int r) { return ps[l] < ps[r]; });
  std::vector<size_t> lcp(n, 0), prev(n, 0), cur(n);
  for (size_t i= 1, j, ed; i < n; lcp[i++]= j)
   for (j= 0, ed= std::min(ps[ord[i - 1]].size(), ps[ord[i]].size()); j < ed; j++)
    if (ps[ord[i - 1]][j] != ps[ord[i]][j]) break;
  size_t nodes= 1;
  for (size_t i= 0; i < n; i++) nodes+= ps[ord[i]].size() - lcp[i];
  bg.reserve(nodes + 1), es.reserve(nodes), match.reserve(nodes), rows.reserve(n + 1);
  for (size_t row= 0; row < n; row++)
   if (!ps[ord[row]].empty()) rows.push_back(row);
  rows.push_back(-1), bg.push_back(0), match.push_back({});
  for (size_t i= 0; i < n && ps[ord[i]].empty(); ++i) match[0].push_back(ord[i]);
  for (size_t col= 0; rows[0] != -1; col++) {
   int size= 0;
   for (int &r: rows) {
    if (r == -1) break;
    size_t row= r;
    if (size++; lcp[row] <= col) {
     if (size_t par= prev[row]; bg[par] == -1) bg[par]= es.size();
     es.push_back(ps[ord[row]][col]), bg.push_back(-1);
     if (match.push_back({}); col + 1 == ps[ord[row]].size())
      for (size_t i= row; i < n && ps[ord[i]] == ps[ord[row]]; ++i) match.back().push_back(ord[i]);
    }
    if (cur[row]= bg.size() - 1; col + 1 == ps[ord[row]].size()) r= -1;
   }
   *std::remove(rows.begin(), rows.begin() + size, -1)= -1, prev.swap(cur);
  }
  bg.push_back(es.size());
  for (size_t i= bg.size() - 1; --i;)
   if (bg[i] == -1) bg[i]= bg[i + 1];
  fail.assign(match.size(), -1);
  for (int u= 0, ed= match.size(); u < ed; u++)
   for (auto i= bg[u], v= i + 1; i < bg[u + 1]; i++, v++) {
    int r= fail[v]= transition(fail[u], es[i]);
    match[v].insert(match[v].end(), match[r].begin(), match[r].end());
   }
 }
 inline int initial_state() const { return 0; }
 inline std::vector<int> matched_patterns(int s) const { return match[s]; }
 inline bool is_accept(int s) const { return !match[s].empty(); }
 inline int transition(int s, symbol_t c) const {
  for (; s >= 0; s= fail[s])
   if (int v= next(s, c); v != -1) return v;
  return 0;
 }
 inline int state_size() const { return match.size(); }
private:
 std::vector<int> bg, fail;
 std::vector<symbol_t> es;
 std::vector<std::vector<int>> match;
 inline int next(int s, symbol_t c) const {
  int index= std::lower_bound(es.begin() + bg[s], es.begin() + bg[s + 1], c) - es.begin();
  if (index != bg[s + 1] && c == es[index]) return index + 1;
  return -1;
 }
};
#line 7 "test/misc/joisc2010_dna.test.cpp"
using namespace std;
int main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 int N;
 cin >> N;
 string S;
 cin >> S;
 int M= S.length();
 vector<string> t(N);
 for (int i= 0; i < N; i++) cin >> t[i];
 AhoCorasick ac(t);
 vector<int> dp(M + 1, 1 << 30);
 dp[0]= 0;
 for (int i= 0, s= ac.initial_state();;) {
  auto ps= ac.matched_patterns(s);
  for (int j: ps) {
   int l= t[j].length();
   if (l == i) dp[i]= 1;
   for (int k= i - 1; k >= 0 && k > i - l; k--) {
    dp[i]= min(dp[i], dp[k] + 1);
   }
  }
  if (i == M) break;
  s= ac.transition(s, S[i++]);
 }
 cout << dp[M] << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	10_1	AC	11 ms	4 MB
g++-13	10_2	AC	63 ms	18 MB
g++-13	10_3	AC	78 ms	22 MB
g++-13	1_1	AC	6 ms	4 MB
g++-13	1_2	AC	6 ms	4 MB
g++-13	1_3	AC	6 ms	4 MB
g++-13	2_1	AC	5 ms	4 MB
g++-13	2_2	AC	6 ms	4 MB
g++-13	2_3	AC	6 ms	4 MB
g++-13	3_1	AC	6 ms	4 MB
g++-13	3_2	AC	6 ms	4 MB
g++-13	3_3	AC	6 ms	4 MB
g++-13	4_1	AC	6 ms	4 MB
g++-13	4_2	AC	19 ms	8 MB
g++-13	4_3	AC	21 ms	9 MB
g++-13	5_1	AC	7 ms	4 MB
g++-13	5_2	AC	22 ms	9 MB
g++-13	5_3	AC	24 ms	10 MB
g++-13	6_1	AC	27 ms	12 MB
g++-13	6_2	AC	27 ms	10 MB
g++-13	6_3	AC	28 ms	11 MB
g++-13	7_1	AC	9 ms	4 MB
g++-13	7_2	AC	46 ms	14 MB
g++-13	7_3	AC	54 ms	16 MB
g++-13	8_1	AC	10 ms	4 MB
g++-13	8_2	AC	56 ms	15 MB
g++-13	8_3	AC	63 ms	18 MB
g++-13	9_1	AC	60 ms	25 MB
g++-13	9_2	AC	58 ms	17 MB
g++-13	9_3	AC	71 ms	20 MB
clang++-18	10_1	AC	11 ms	4 MB
clang++-18	10_2	AC	62 ms	18 MB
clang++-18	10_3	AC	73 ms	22 MB
clang++-18	1_1	AC	5 ms	4 MB
clang++-18	1_2	AC	6 ms	4 MB
clang++-18	1_3	AC	6 ms	4 MB
clang++-18	2_1	AC	5 ms	4 MB
clang++-18	2_2	AC	6 ms	4 MB
clang++-18	2_3	AC	6 ms	4 MB
clang++-18	3_1	AC	6 ms	4 MB
clang++-18	3_2	AC	6 ms	4 MB
clang++-18	3_3	AC	6 ms	4 MB
clang++-18	4_1	AC	6 ms	4 MB
clang++-18	4_2	AC	18 ms	8 MB
clang++-18	4_3	AC	20 ms	9 MB
clang++-18	5_1	AC	6 ms	4 MB
clang++-18	5_2	AC	22 ms	9 MB
clang++-18	5_3	AC	24 ms	10 MB
clang++-18	6_1	AC	27 ms	12 MB
clang++-18	6_2	AC	28 ms	10 MB
clang++-18	6_3	AC	29 ms	11 MB
clang++-18	7_1	AC	9 ms	4 MB
clang++-18	7_2	AC	46 ms	14 MB
clang++-18	7_3	AC	53 ms	17 MB
clang++-18	8_1	AC	10 ms	4 MB
clang++-18	8_2	AC	52 ms	16 MB
clang++-18	8_3	AC	60 ms	18 MB
clang++-18	9_1	AC	61 ms	25 MB
clang++-18	9_2	AC	64 ms	17 MB
clang++-18	9_3	AC	69 ms	20 MB

Back to top page