#828065 (Rust) No.2172 SEARCH in the Text Editor

提出ソース

結果

問題	No.2172 SEARCH in the Text Editor
ユーザー	akakimidori
提出日時	2022-12-24 00:13:53
言語	Rust (1.77.0)
結果	AC
実行時間	144 ms / 2,000 ms
コード長	11,330 bytes
コンパイル時間	6,412 ms
コンパイル使用メモリ	168,644 KB
実行使用メモリ	87,676 KB
最終ジャッジ日時	2023-08-11 13:40:10
合計ジャッジ時間	8,327 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,384 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	126 ms 87,660 KB
testcase_04	AC	113 ms 87,588 KB
testcase_05	AC	114 ms 87,676 KB
testcase_06	AC	13 ms 6,348 KB
testcase_07	AC	11 ms 5,800 KB
testcase_08	AC	12 ms 6,116 KB
testcase_09	AC	35 ms 18,228 KB
testcase_10	AC	35 ms 17,152 KB
testcase_11	AC	48 ms 33,920 KB
testcase_12	AC	16 ms 7,436 KB
testcase_13	AC	20 ms 9,180 KB
testcase_14	AC	30 ms 14,408 KB
testcase_15	AC	22 ms 12,620 KB
testcase_16	AC	16 ms 7,388 KB
testcase_17	AC	16 ms 7,212 KB
testcase_18	AC	39 ms 20,572 KB
testcase_19	AC	22 ms 9,740 KB
testcase_20	AC	13 ms 6,928 KB
testcase_21	AC	96 ms 69,220 KB
testcase_22	AC	26 ms 12,616 KB
testcase_23	AC	28 ms 14,176 KB
testcase_24	AC	34 ms 17,248 KB
testcase_25	AC	34 ms 17,192 KB
testcase_26	AC	125 ms 87,668 KB
testcase_27	AC	125 ms 87,656 KB
testcase_28	AC	29 ms 11,580 KB
testcase_29	AC	30 ms 13,104 KB
testcase_30	AC	36 ms 16,256 KB
testcase_31	AC	34 ms 16,208 KB
testcase_32	AC	144 ms 86,636 KB
testcase_33	AC	143 ms 86,636 KB
testcase_34	AC	25 ms 12,532 KB
testcase_35	AC	27 ms 14,140 KB
testcase_36	AC	30 ms 17,236 KB
testcase_37	AC	30 ms 17,264 KB
testcase_38	AC	111 ms 87,676 KB
testcase_39	AC	112 ms 87,588 KB
testcase_40	AC	27 ms 11,584 KB
testcase_41	AC	30 ms 13,144 KB
testcase_42	AC	33 ms 16,272 KB
testcase_43	AC	31 ms 16,252 KB
testcase_44	AC	122 ms 86,644 KB
testcase_45	AC	124 ms 86,564 KB
testcase_46	AC	78 ms 48,692 KB
testcase_47	AC	53 ms 36,008 KB
testcase_48	AC	56 ms 37,868 KB
testcase_49	AC	90 ms 63,668 KB
testcase_50	AC	82 ms 59,636 KB
testcase_51	AC	44 ms 33,888 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: type alias `Map` is never used
   --> Main.rs:374:6
    |
374 | type Map<K, V> = BTreeMap<K, V>;
    |      ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
   --> Main.rs:375:6
    |
375 | type Set<T> = BTreeSet<T>;
    |      ^^^

warning: type alias `Deque` is never used
   --> Main.rs:376:6
    |
376 | type Deque<T> = VecDeque<T>;
    |      ^^^^^

warning: 3 warnings emitted

ソースコード

raw source code

// ---------- begin modint ----------
use std::marker::*;
use std::ops::*;

pub trait Modulo {
    fn modulo() -> u32;
}

pub struct ConstantModulo<const M: u32>;

impl<const M: u32> Modulo for ConstantModulo<{ M }> {
    fn modulo() -> u32 {
        M
    }
}

pub struct ModInt<T>(u32, PhantomData<T>);

impl<T> Clone for ModInt<T> {
    fn clone(&self) -> Self {
        Self::new_unchecked(self.0)
    }
}

impl<T> Copy for ModInt<T> {}

impl<T: Modulo> Add for ModInt<T> {
    type Output = ModInt<T>;
    fn add(self, rhs: Self) -> Self::Output {
        let mut v = self.0 + rhs.0;
        if v >= T::modulo() {
            v -= T::modulo();
        }
        Self::new_unchecked(v)
    }
}

impl<T: Modulo> AddAssign for ModInt<T> {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl<T: Modulo> Sub for ModInt<T> {
    type Output = ModInt<T>;
    fn sub(self, rhs: Self) -> Self::Output {
        let mut v = self.0 - rhs.0;
        if self.0 < rhs.0 {
            v += T::modulo();
        }
        Self::new_unchecked(v)
    }
}

impl<T: Modulo> SubAssign for ModInt<T> {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<T: Modulo> Mul for ModInt<T> {
    type Output = ModInt<T>;
    fn mul(self, rhs: Self) -> Self::Output {
        let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;
        Self::new_unchecked(v as u32)
    }
}

impl<T: Modulo> MulAssign for ModInt<T> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<T: Modulo> Neg for ModInt<T> {
    type Output = ModInt<T>;
    fn neg(self) -> Self::Output {
        if self.is_zero() {
            Self::zero()
        } else {
            Self::new_unchecked(T::modulo() - self.0)
        }
    }
}

impl<T> std::fmt::Display for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl<T> std::fmt::Debug for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl<T> Default for ModInt<T> {
    fn default() -> Self {
        Self::zero()
    }
}

impl<T: Modulo> std::str::FromStr for ModInt<T> {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

impl<T: Modulo> From<usize> for ModInt<T> {
    fn from(val: usize) -> ModInt<T> {
        ModInt::new_unchecked((val % T::modulo() as usize) as u32)
    }
}

impl<T: Modulo> From<u64> for ModInt<T> {
    fn from(val: u64) -> ModInt<T> {
        ModInt::new_unchecked((val % T::modulo() as u64) as u32)
    }
}

impl<T: Modulo> From<i64> for ModInt<T> {
    fn from(val: i64) -> ModInt<T> {
        let mut v = ((val % T::modulo() as i64) + T::modulo() as i64) as u32;
        if v >= T::modulo() {
            v -= T::modulo();
        }
        ModInt::new_unchecked(v)
    }
}

impl<T> ModInt<T> {
    pub fn new_unchecked(n: u32) -> Self {
        ModInt(n, PhantomData)
    }
    pub fn zero() -> Self {
        ModInt::new_unchecked(0)
    }
    pub fn one() -> Self {
        ModInt::new_unchecked(1)
    }
    pub fn is_zero(&self) -> bool {
        self.0 == 0
    }
}

impl<T: Modulo> ModInt<T> {
    pub fn new(d: u32) -> Self {
        ModInt::new_unchecked(d % T::modulo())
    }
    pub fn pow(&self, mut n: u64) -> Self {
        let mut t = Self::one();
        let mut s = *self;
        while n > 0 {
            if n & 1 == 1 {
                t *= s;
            }
            s *= s;
            n >>= 1;
        }
        t
    }
    pub fn inv(&self) -> Self {
        assert!(!self.is_zero());
        self.pow(T::modulo() as u64 - 2)
    }
    pub fn fact(n: usize) -> Self {
        (1..=n).fold(Self::one(), |s, a| s * Self::from(a))
    }
    pub fn perm(n: usize, k: usize) -> Self {
        if k > n {
            return Self::zero();
        }
        ((n - k + 1)..=n).fold(Self::one(), |s, a| s * Self::from(a))
    }
    pub fn binom(n: usize, k: usize) -> Self {
        if k > n {
            return Self::zero();
        }
        let k = k.min(n - k);
        let mut nu = Self::one();
        let mut de = Self::one();
        for i in 0..k {
            nu *= Self::from(n - i);
            de *= Self::from(i + 1);
        }
        nu * de.inv()
    }
}
// ---------- end modint ----------
// ---------- begin precalc ----------
pub struct Precalc<T> {
    fact: Vec<ModInt<T>>,
    ifact: Vec<ModInt<T>>,
    inv: Vec<ModInt<T>>,
}

impl<T: Modulo> Precalc<T> {
    pub fn new(n: usize) -> Precalc<T> {
        let mut inv = vec![ModInt::one(); n + 1];
        let mut fact = vec![ModInt::one(); n + 1];
        let mut ifact = vec![ModInt::one(); n + 1];
        for i in 2..=n {
            fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32);
        }
        ifact[n] = fact[n].inv();
        if n > 0 {
            inv[n] = ifact[n] * fact[n - 1];
        }
        for i in (1..n).rev() {
            ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32);
            inv[i] = ifact[i] * fact[i - 1];
        }
        Precalc { fact, ifact, inv }
    }
    pub fn inv(&self, n: usize) -> ModInt<T> {
        assert!(n > 0);
        self.inv[n]
    }
    pub fn fact(&self, n: usize) -> ModInt<T> {
        self.fact[n]
    }
    pub fn ifact(&self, n: usize) -> ModInt<T> {
        self.ifact[n]
    }
    pub fn perm(&self, n: usize, k: usize) -> ModInt<T> {
        if k > n {
            return ModInt::zero();
        }
        self.fact[n] * self.ifact[n - k]
    }
    pub fn binom(&self, n: usize, k: usize) -> ModInt<T> {
        if k > n {
            return ModInt::zero();
        }
        self.fact[n] * self.ifact[k] * self.ifact[n - k]
    }
}
// ---------- end precalc ----------

type M = ModInt<ConstantModulo<998_244_353>>;

// ---------- begin Aho-Corasick ----------
const F: usize = 62;

struct ACTrieNode {
    fail: usize,
    next: [usize; F],
}

impl Default for ACTrieNode {
    fn default() -> Self {
        let fail = 0;
        let next = [0; F];
        ACTrieNode {
            fail, next,
        }
    }
}

pub struct AhoCorasick {
    node: Vec<ACTrieNode>,
}

impl AhoCorasick {
    pub fn new() -> Self {
        AhoCorasick {
            node: vec![ACTrieNode::default()],
        }
    }
    pub fn insert(&mut self, s: &[usize]) -> usize {
        let node = &mut self.node;
        let mut v = 0;
        for &k in s {
            if node[v].next[k] == 0 {
                node[v].next[k] = node.len();
                node.push(ACTrieNode::default());
            }
            v = node[v].next[k];
        }
        v
    }
    pub fn build(&mut self) {
        let mut q = std::collections::VecDeque::new();
        let node = &mut self.node;
        for i in 0..F {
            if node[0].next[i] != 0 {
                q.push_back(node[0].next[i]);
            }
        }
        while let Some(v) = q.pop_front() {
            for i in 0..F {
                let u = node[v].next[i];
                if u == 0 {
                    continue;
                }
                let mut fail = node[v].fail;
                while fail > 0 && node[fail].next[i] == 0 {
                    fail = node[fail].fail;
                }
                let f = node[fail].next[i];
                node[u].fail = f;
                q.push_back(u);
            }
        }
    }
    pub fn next(&self, v: usize, k: usize) -> usize {
        assert!(v < self.node.len() && k < F);
        self.node[v].next[k]
    }
    pub fn trans(&self, mut v: usize, k: usize) -> usize {
        assert!(v < self.node.len() && k < F);
        let node = &self.node;
        while v > 0 && node[v].next[k] == 0 {
            v = node[v].fail;
        }
        node[v].next[k]
    }
    pub fn fail(&self, v: usize) -> usize {
        assert!(v < self.node.len());
        self.node[v].fail
    }
    pub fn size(&self) -> usize {
        self.node.len()
    }
    pub fn bfs<F: FnMut(usize, &[usize], usize)>(&self, mut f: F) {
        let mut q = std::collections::VecDeque::new();
        q.push_back(0);
        while let Some(v) = q.pop_front() {
            f(v, &self.node[v].next, self.node[v].fail);
            for &u in self.node[v].next.iter() {
                if u != 0 {
                    q.push_back(u);
                }
            }
        }
    }
}
// ---------- end Aho-Corasick ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let index = |x: u8| -> usize {
        let c = if b'a' <= x && x <= b'z' {
            x - b'a'
        } else if b'A' <= x && x <= b'Z' {
            x - b'A' + 26
        } else {
            x - b'0' + 52
        };
        c as usize
    };
    let t = sc.next_bytes();
    let t = t.into_iter().map(index).collect::<Vec<_>>();
    let mut aho = AhoCorasick::new();
    let pos = aho.insert(&t);
    aho.build();
    let mut hit = vec![false; pos + 1];
    hit[pos] = true;
    let mut trans = vec![];
    for _ in 0..n {
        let s = sc.next_bytes();
        if s[0] != b'~' {
            let s = s.into_iter().map(index).collect::<Vec<_>>();
            let mut memo = (0..hit.len()).map(|x| (x, M::zero())).collect::<Vec<_>>();
            for memo in memo.iter_mut() {
                for c in s.iter() {
                    memo.0 = aho.trans(memo.0, *c);
                    if memo.0 == pos {
                        memo.1 += M::one();
                    }
                }
            }
            trans.push(memo);
        } else {
            let j = sc.next::<usize>() - 1;
            let k = sc.next::<usize>() - 1;
            let mut a = trans[j].clone();
            for a in a.iter_mut() {
                a.1 += trans[k][a.0].1;
                a.0 = trans[k][a.0].0;
            }
            trans.push(a);
        }
    }
    writeln!(out, "{}", trans[n - 1][0].1).ok();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード