verification/library-checker/aho_corasick/src/main.rs

• View this file on GitHub
• Last update: 2026-01-01 00:11:18+09:00
• Problem: https://judge.yosupo.jp/problem/aho_corasick

Depends on

• Aho-Corasick algorithm (string/aho-corasick/src/lib.rs)

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/aho_corasick

use itertools::Itertools;
use proconio::{input, marker::Chars};

use aho_corasick::AhoCorasick;

fn main() {
    input! {
        n: usize,
        s: [Chars; n],
    }
    let mut ac = AhoCorasick::new(26, 'a');
    (0..n).for_each(|i| ac.insert(&s[i]));
    ac.build(true);

    let mut index = vec![None; s.iter().map(|s| s.len()).sum::<usize>() + 1];
    index[0] = Some(0);
    let mut ps = vec![(0, 0)];
    let mut v = vec![];
    for i in 0..n {
        let mut now = 0;
        for &c in &s[i] {
            let (_, next) = ac.next(c, now);
            let (_, fail) = ac.next((26 + 'a' as u8) as char, next);
            if index[next].is_none() {
                index[next] = Some(ps.len());
                ps.push((now, fail));
            }
            now = next;
        }
        v.push(now);
    }

    println!("{}", ps.len());
    for &(p, s) in &ps[1..] {
        let p = index[p].unwrap();
        let s = index[s].unwrap();
        println!("{} {}", p, s);
    }
    println!("{}", v.iter().map(|&v| index[v].unwrap()).join(" "));
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	almost_single_00	AC	1492 ms	548 MB
Rust	almost_single_01	AC	1512 ms	548 MB
Rust	almost_single_02	AC	1491 ms	548 MB
Rust	almost_single_03	AC	1377 ms	459 MB
Rust	almost_single_04	AC	1474 ms	548 MB
Rust	almost_single_05	AC	1506 ms	548 MB
Rust	almost_single_06	AC	1430 ms	519 MB
Rust	almost_single_07	AC	1219 ms	408 MB
Rust	bfs_00	AC	43 ms	15 MB
Rust	bfs_01	AC	262 ms	60 MB
Rust	bfs_02	AC	521 ms	109 MB
Rust	bfs_03	AC	808 ms	170 MB
Rust	example_00	AC	7 ms	2 MB
Rust	example_01	AC	6 ms	2 MB
Rust	example_02	AC	5 ms	2 MB
Rust	example_03	AC	5 ms	2 MB
Rust	fibonacci_00	AC	1528 ms	548 MB
Rust	fibonacci_01	AC	1484 ms	547 MB
Rust	fibonacci_02	AC	1560 ms	548 MB
Rust	fibonacci_03	AC	1630 ms	540 MB
Rust	fibonacci_04	AC	1499 ms	548 MB
Rust	fibonacci_05	AC	1566 ms	549 MB
Rust	fibonacci_06	AC	1618 ms	546 MB
Rust	fibonacci_07	AC	1580 ms	544 MB
Rust	fibonacci_08	AC	1478 ms	548 MB
Rust	fibonacci_09	AC	1546 ms	546 MB
Rust	fibonacci_10	AC	1569 ms	546 MB
Rust	fibonacci_11	AC	1611 ms	536 MB
Rust	fibonacci_12	AC	1509 ms	548 MB
Rust	fibonacci_13	AC	1555 ms	546 MB
Rust	fibonacci_14	AC	1578 ms	548 MB
Rust	fibonacci_15	AC	1635 ms	541 MB
Rust	random_00	AC	173 ms	74 MB
Rust	random_01	AC	170 ms	64 MB
Rust	random_02	AC	4601 ms	3224 MB
Rust	random_03	AC	3280 ms	1621 MB
Rust	random_04	AC	1483 ms	547 MB
Rust	random_05	AC	1510 ms	548 MB
Rust	random_06	AC	1557 ms	545 MB
Rust	random_07	AC	1594 ms	546 MB
Rust	random_08	AC	180 ms	76 MB
Rust	random_09	AC	151 ms	58 MB
Rust	random_10	AC	7969 ms	6159 MB
Rust	random_11	AC	2412 ms	594 MB
Rust	random_12	AC	1496 ms	548 MB
Rust	random_13	AC	1512 ms	546 MB
Rust	random_14	AC	1555 ms	547 MB
Rust	random_15	AC	1636 ms	551 MB
Rust	random_16	AC	171 ms	74 MB
Rust	random_17	AC	277 ms	121 MB
Rust	random_18	AC	624 ms	312 MB
Rust	random_19	AC	2795 ms	874 MB
Rust	random_20	AC	1538 ms	548 MB
Rust	random_21	AC	1471 ms	547 MB
Rust	random_22	AC	1507 ms	545 MB
Rust	random_23	AC	1639 ms	546 MB
Rust	short_period_00	AC	1517 ms	547 MB
Rust	short_period_01	AC	893 ms	301 MB
Rust	short_period_02	AC	1228 ms	453 MB
Rust	short_period_03	AC	248 ms	90 MB
Rust	short_period_04	AC	1493 ms	547 MB
Rust	short_period_05	AC	1597 ms	554 MB
Rust	short_period_06	AC	723 ms	220 MB
Rust	short_period_07	AC	260 ms	86 MB
Rust	short_period_08	AC	1533 ms	548 MB
Rust	short_period_09	AC	1546 ms	549 MB
Rust	short_period_10	AC	922 ms	287 MB
Rust	short_period_11	AC	599 ms	165 MB
Rust	short_period_12	AC	1541 ms	548 MB
Rust	short_period_13	AC	1548 ms	547 MB
Rust	short_period_14	AC	1562 ms	543 MB
Rust	short_period_15	AC	1403 ms	458 MB

Back to top page