結果

問題 No.2761 Substitute and Search
コンテスト
ユーザー magurofly
提出日時 2024-05-06 00:01:42
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 560 ms / 4,000 ms
コード長 3,157 bytes
コンパイル時間 13,638 ms
コンパイル使用メモリ 398,848 KB
実行使用メモリ 354,816 KB
最終ジャッジ日時 2024-11-29 18:27:27
合計ジャッジ時間 18,214 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::{Chars, Usize1}};
use std::num::*;

struct TrieNode {
    pub children: [Option<NonZeroU32>; 26],
    pub sum: usize,
}
impl TrieNode {
    pub fn new() -> Self {
        Self {
            children: [None; 26],
            sum: 0,
        }
    }
}

struct Trie {
    nodes: Vec<TrieNode>,
    subst: Vec<Vec<Vec<u8>>>,
}
impl Trie {
    pub fn new(l: usize) -> Self {
        Self {
            nodes: vec![TrieNode::new()],
            subst: vec![(0 .. 26).map(|i| vec![i] ).collect(); l],
        }
    }

    pub fn add(&mut self, s: &[usize]) {
        let mut cur = 0;
        self.nodes[cur].sum += 1;
        for k in 0 .. s.len() {
            let c = s[k];
            if self.nodes[cur].children[c].is_none() {
                let id = self.nodes.len();
                self.nodes.push(TrieNode::new());
                self.nodes[cur].children[c] = NonZeroU32::new(id as u32);
            }
            cur = self.nodes[cur].children[c].unwrap().get() as usize;
            self.nodes[cur].sum += 1;
        }
    }

    pub fn substitute(&mut self, k: usize, c: usize, d: usize) {
        let mut src = std::mem::take(&mut self.subst[k][c]);
        self.subst[k][d].append(&mut src);
    }

    pub fn search(&mut self, s: &[usize]) -> usize {
        let mut cur = 0;
        for k in 0 .. s.len() {
            let d = s[k];
            let mut next = None;
            for c in self.subst[k][d].clone() {
                if let Some(id) = self.nodes[cur].children[c as usize] {
                    if let Some(next_id) = next {
                        self.merge(next_id, id.get() as usize);
                        self.nodes[cur].children[c as usize] = None;
                    } else {
                        next = Some(id.get() as usize);
                    }
                }
            }
            if let Some(id) = next {
                cur = id;
            } else {
                return 0;
            }
        }
        self.nodes[cur].sum
    }

    fn merge(&mut self, dst: usize, src: usize) {
        self.nodes[dst].sum += self.nodes[src].sum;
        for c in 0 .. 26 {
            if let Some(src_child) = self.nodes[src].children[c] {
                if let Some(dst_child) = self.nodes[dst].children[c] {
                    self.merge(dst_child.get() as usize, src_child.get() as usize);
                } else {
                    self.nodes[dst].children[c] = Some(src_child);
                }
            }
        }
    }
}

fn convert(s: &[char]) -> Vec<usize> {
    s.iter().map(|&c| (c as u8 - b'a') as usize ).collect()
}

fn main() {
    input! {
        n: usize, l: usize, q: usize,
        strs: [Chars; n],
    }

    let mut trie = Trie::new(l);
    for s in strs {
        trie.add(&convert(&s));
    }

    for _ in 0 .. q {
        input!(qtype: usize);
        if qtype == 1 {
            input!(k: Usize1, c: char, d: char);
            trie.substitute(k, (c as u8 - b'a') as usize, (d as u8 - b'a') as usize);
        } else {
            input!(t: Chars);
            let ans = trie.search(&convert(&t));
            println!("{ans}");
        }
    }
}
0