結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 Haar
|
| 提出日時 | 2025-03-17 18:05:43 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 18 ms / 2,000 ms |
| コード長 | 13,475 bytes |
| コンパイル時間 | 14,424 ms |
| コンパイル使用メモリ | 400,988 KB |
| 実行使用メモリ | 7,680 KB |
| 最終ジャッジ日時 | 2025-03-17 18:05:59 |
| 合計ジャッジ時間 | 14,963 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
// Bundled at 2025/03/17 18:05:05 +09:00
// Author: Haar
pub mod main {
use super::*;
use haar_lib::algo::aho_corasick::*;
#[allow(unused_imports)]
use haar_lib::{get, input, iter::join_str::*, utils::fastio::*};
#[allow(unused_imports)]
use std::cell::{Cell, RefCell};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
let s = io.read_chars();
let m = io.read_usize();
let mut ac = AhoCorasickBuilder::new();
for _ in 0..m {
let c = io.read_chars();
let c = c.into_iter().collect::<String>();
ac.add(&c);
}
let ac = ac.build();
let s = s.into_iter().collect::<String>();
let mut ans = 0;
ac.matches(&s, |_, _| ans += 1);
io.writeln(ans);
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod algo {
pub mod aho_corasick {
use std::collections::{HashMap, VecDeque};
pub struct Node {
index: usize,
children: HashMap<char, *mut Self>,
failure_link: Option<*mut Self>,
rev_failure_links: Vec<*mut Self>,
}
impl Node {
fn new(index: usize) -> Self {
Self {
index,
children: HashMap::new(),
failure_link: None,
rev_failure_links: vec![],
}
}
pub fn index(&self) -> usize {
self.index
}
pub fn child(&self, c: char) -> Option<&Self> {
self.children.get(&c).map(|&p| {
assert!(!p.is_null());
unsafe { &*p }
})
}
pub fn failure_link(&self) -> Option<&Self> {
self.failure_link.map(|p| {
assert!(!p.is_null());
unsafe { &*p }
})
}
pub fn rev_failure_link(&self) -> impl Iterator<Item = &Self> {
self.rev_failure_links.iter().map(|&p| {
assert!(!p.is_null());
unsafe { &*p }
})
}
}
fn index_of(p: *mut Node) -> usize {
assert!(!p.is_null());
unsafe { (*p).index }
}
fn child_of(p: *mut Node, c: char) -> Option<*mut Node> {
assert!(!p.is_null());
unsafe { (*p).children.get(&c).copied() }
}
fn failure_link_of(p: *mut Node) -> Option<*mut Node> {
assert!(!p.is_null());
unsafe { (*p).failure_link }
}
fn set_failure_link(from: *mut Node, to: *mut Node) {
assert!(!from.is_null());
unsafe {
(*from).failure_link = Some(to);
(*to).rev_failure_links.push(from);
}
}
pub struct AhoCorasickBuilder {
size: usize,
root: *mut Node,
dict: Vec<String>,
dict_index: Vec<Vec<usize>>,
nodes: Vec<*mut Node>,
}
impl AhoCorasickBuilder {
pub fn new() -> Self {
let root = Box::new(Node::new(0));
let root = Box::into_raw(root);
Self {
size: 1,
root,
dict: vec![],
dict_index: vec![],
nodes: vec![],
}
}
pub fn add(&mut self, pat: &str) {
self.dict.push(pat.to_owned());
let mut cur = self.root;
for c in pat.chars() {
assert!(!cur.is_null());
if let Some(next) = child_of(cur, c) {
cur = next;
} else {
let new = Box::new(Node::new(self.size));
let new = Box::into_raw(new);
assert!(!cur.is_null());
unsafe { (*cur).children.insert(c, new) };
cur = new;
self.size += 1;
}
}
self.nodes.push(cur);
self.dict_index.resize(self.size, vec![]);
self.dict_index[index_of(cur)].push(self.dict.len() - 1);
}
pub fn build(self) -> AhoCorasick {
let mut dq = VecDeque::new();
dq.push_back(self.root);
while let Some(cur) = dq.pop_front() {
assert!(!cur.is_null());
for (&c, &next) in unsafe { (*cur).children.iter() } {
if cur == self.root {
set_failure_link(next, cur);
} else {
let mut i = failure_link_of(cur).unwrap();
let mut j = self.root;
loop {
if let Some(t) = child_of(i, c) {
j = t;
break;
}
let Some(t) = failure_link_of(i) else {
break;
};
i = t;
}
set_failure_link(next, j);
}
dq.push_back(next);
}
}
AhoCorasick {
size: self.size,
root: self.root,
dict: self.dict,
dict_index: self.dict_index,
nodes: self.nodes,
}
}
}
pub struct AhoCorasick {
size: usize,
root: *mut Node,
dict: Vec<String>,
dict_index: Vec<Vec<usize>>,
nodes: Vec<*mut Node>,
}
impl AhoCorasick {
pub fn len(&self) -> usize {
self.size
}
pub fn root_node(&self) -> &Node {
unsafe { &*self.root }
}
pub fn node_of(&self, index: usize) -> &Node {
assert!(!self.nodes[index].is_null());
unsafe { &*self.nodes[index] }
}
pub fn matches<F>(&self, s: &str, mut proc: F)
where
F: FnMut(usize, std::ops::Range<usize>),
{
let mut cur = self.root;
for (i, c) in s.chars().enumerate() {
while cur != self.root && unsafe { !(*cur).children.contains_key(&c) } {
cur = failure_link_of(cur).unwrap();
}
cur = child_of(cur, c).unwrap_or(self.root);
let mut p = cur;
loop {
for &j in &self.dict_index[index_of(p)] {
let len = self.dict[j].len();
proc(j, i + 1 - len..i + 1);
}
let Some(q) = failure_link_of(p) else { break };
p = q;
}
}
}
}
}
}
pub mod iter {
pub mod join_str {
pub trait JoinStr: Iterator {
fn join_str(self, s: &str) -> String
where
Self: Sized,
Self::Item: ToString,
{
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
impl<I> JoinStr for I where I: Iterator + ?Sized {}
}
}
pub mod macros {
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
let c = *self.in_bytes.get(self.in_cur)?;
self.in_cur += 1;
Some(c)
}
#[inline]
pub fn peek(&self) -> Option<u8> {
Some(*self.in_bytes.get(self.in_cur)?)
}
#[inline]
pub fn skip(&mut self) {
while self.peek().is_some_and(|c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
}