test/aoj/2873.test.cpp

• View this file on GitHub
• Last update: 2024-10-01 21:03:13+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2873

Depends on

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

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2873
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include "src/String/AhoCorasick.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string S;
 cin >> S;
 int N;
 cin >> N;
 vector<string> P(N);
 for (int i= 0; i < N; ++i) cin >> P[i];
 AhoCorasick aho(P);
 int n= S.length();
 int ans= 0;
 for (int i= 0, s= aho.initial_state(); i < n; ++i) {
  int ns= aho.transition(s, S[i]);
  if (aho.is_accept(ns)) ++ans, ns= aho.initial_state();
  s= ns;
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/2873.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2873
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#line 4 "src/String/AhoCorasick.hpp"
#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 8 "test/aoj/2873.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string S;
 cin >> S;
 int N;
 cin >> N;
 vector<string> P(N);
 for (int i= 0; i < N; ++i) cin >> P[i];
 AhoCorasick aho(P);
 int n= S.length();
 int ans= 0;
 for (int i= 0, s= aho.initial_state(); i < n; ++i) {
  int ns= aho.transition(s, S[i]);
  if (aho.is_accept(ns)) ++ans, ns= aho.initial_state();
  s= ns;
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	7 ms	4 MB
g++-13	00_sample_01.in	AC	5 ms	4 MB
g++-13	00_sample_02.in	AC	5 ms	4 MB
g++-13	10_random_00.in	AC	10 ms	5 MB
g++-13	10_random_01.in	AC	13 ms	6 MB
g++-13	10_random_02.in	AC	10 ms	4 MB
g++-13	10_random_03.in	AC	9 ms	4 MB
g++-13	10_random_04.in	AC	11 ms	6 MB
g++-13	10_random_05.in	AC	13 ms	5 MB
g++-13	10_random_06.in	AC	9 ms	5 MB
g++-13	10_random_07.in	AC	10 ms	5 MB
g++-13	10_random_08.in	AC	7 ms	4 MB
g++-13	10_random_09.in	AC	15 ms	6 MB
g++-13	10_random_10.in	AC	9 ms	5 MB
g++-13	10_random_11.in	AC	8 ms	4 MB
g++-13	10_random_12.in	AC	8 ms	4 MB
g++-13	10_random_13.in	AC	10 ms	5 MB
g++-13	10_random_14.in	AC	8 ms	4 MB
g++-13	10_random_15.in	AC	11 ms	5 MB
g++-13	10_random_16.in	AC	10 ms	4 MB
g++-13	10_random_17.in	AC	11 ms	5 MB
g++-13	10_random_18.in	AC	9 ms	4 MB
g++-13	10_random_19.in	AC	9 ms	5 MB
g++-13	20_rep_00.in	AC	10 ms	5 MB
g++-13	20_rep_01.in	AC	8 ms	4 MB
g++-13	20_rep_02.in	AC	10 ms	5 MB
g++-13	20_rep_03.in	AC	7 ms	4 MB
g++-13	20_rep_04.in	AC	8 ms	4 MB
g++-13	20_rep_05.in	AC	10 ms	4 MB
g++-13	20_rep_06.in	AC	8 ms	4 MB
g++-13	20_rep_07.in	AC	13 ms	5 MB
g++-13	20_rep_08.in	AC	13 ms	5 MB
g++-13	20_rep_09.in	AC	12 ms	5 MB
g++-13	30_palindrome_00.in	AC	10 ms	5 MB
g++-13	30_palindrome_01.in	AC	11 ms	5 MB
g++-13	30_palindrome_02.in	AC	9 ms	5 MB
g++-13	30_palindrome_03.in	AC	7 ms	4 MB
g++-13	30_palindrome_04.in	AC	9 ms	5 MB
g++-13	30_palindrome_05.in	AC	10 ms	4 MB
g++-13	30_palindrome_06.in	AC	13 ms	5 MB
g++-13	30_palindrome_07.in	AC	11 ms	4 MB
g++-13	30_palindrome_08.in	AC	32 ms	4 MB
g++-13	30_palindrome_09.in	AC	9 ms	4 MB
g++-13	90_challenge_00.in	AC	56 ms	4 MB
g++-13	91_tsutaj_00.in	AC	42 ms	4 MB
clang++-18	00_sample_00.in	AC	6 ms	4 MB
clang++-18	00_sample_01.in	AC	5 ms	4 MB
clang++-18	00_sample_02.in	AC	5 ms	4 MB
clang++-18	10_random_00.in	AC	10 ms	5 MB
clang++-18	10_random_01.in	AC	14 ms	6 MB
clang++-18	10_random_02.in	AC	10 ms	5 MB
clang++-18	10_random_03.in	AC	9 ms	4 MB
clang++-18	10_random_04.in	AC	11 ms	6 MB
clang++-18	10_random_05.in	AC	13 ms	5 MB
clang++-18	10_random_06.in	AC	9 ms	5 MB
clang++-18	10_random_07.in	AC	10 ms	5 MB
clang++-18	10_random_08.in	AC	7 ms	4 MB
clang++-18	10_random_09.in	AC	15 ms	6 MB
clang++-18	10_random_10.in	AC	9 ms	5 MB
clang++-18	10_random_11.in	AC	9 ms	4 MB
clang++-18	10_random_12.in	AC	8 ms	5 MB
clang++-18	10_random_13.in	AC	10 ms	5 MB
clang++-18	10_random_14.in	AC	8 ms	4 MB
clang++-18	10_random_15.in	AC	11 ms	5 MB
clang++-18	10_random_16.in	AC	11 ms	5 MB
clang++-18	10_random_17.in	AC	11 ms	5 MB
clang++-18	10_random_18.in	AC	9 ms	4 MB
clang++-18	10_random_19.in	AC	10 ms	5 MB
clang++-18	20_rep_00.in	AC	10 ms	5 MB
clang++-18	20_rep_01.in	AC	8 ms	4 MB
clang++-18	20_rep_02.in	AC	10 ms	5 MB
clang++-18	20_rep_03.in	AC	8 ms	4 MB
clang++-18	20_rep_04.in	AC	8 ms	4 MB
clang++-18	20_rep_05.in	AC	10 ms	4 MB
clang++-18	20_rep_06.in	AC	9 ms	4 MB
clang++-18	20_rep_07.in	AC	13 ms	6 MB
clang++-18	20_rep_08.in	AC	14 ms	5 MB
clang++-18	20_rep_09.in	AC	13 ms	5 MB
clang++-18	30_palindrome_00.in	AC	10 ms	5 MB
clang++-18	30_palindrome_01.in	AC	11 ms	5 MB
clang++-18	30_palindrome_02.in	AC	9 ms	5 MB
clang++-18	30_palindrome_03.in	AC	7 ms	4 MB
clang++-18	30_palindrome_04.in	AC	9 ms	5 MB
clang++-18	30_palindrome_05.in	AC	8 ms	4 MB
clang++-18	30_palindrome_06.in	AC	10 ms	5 MB
clang++-18	30_palindrome_07.in	AC	9 ms	4 MB
clang++-18	30_palindrome_08.in	AC	8 ms	4 MB
clang++-18	30_palindrome_09.in	AC	7 ms	4 MB
clang++-18	90_challenge_00.in	AC	5 ms	4 MB
clang++-18	91_tsutaj_00.in	AC	6 ms	4 MB

Back to top page