結果

問題 No.2761 Substitute and Search
コンテスト
ユーザー magurofly
提出日時 2024-05-05 23:56:10
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,027 bytes
コンパイル時間 13,913 ms
コンパイル使用メモリ 383,572 KB
実行使用メモリ 814,716 KB
最終ジャッジ日時 2024-11-29 18:20:14
合計ジャッジ時間 25,669 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::{Chars, Usize1}};

struct TrieNode {
    pub children: [Option<usize>; 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<usize>>>,
}
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] = Some(id);
            }
            cur = self.nodes[cur].children[c].unwrap();
            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] {
                    if let Some(next_id) = next {
                        self.merge(next_id, id);
                        self.nodes[cur].children[c] = None;
                    } else {
                        next = Some(id);
                    }
                }
            }
            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, src_child);
                } 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