結果

問題 No.430 文字列検索
コンテスト
ユーザー akakimidori
提出日時 2019-10-05 02:13:11
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,449 bytes
コンパイル時間 12,767 ms
コンパイル使用メモリ 379,836 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2024-11-10 00:35:51
合計ジャッジ時間 11,420 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;

const F: usize = 26;
type Link = Option<Box<Node>>;
struct Node {
    cnt: u32,
    next: [Link; F],
}

fn insert(mut t: Link, s: &[usize]) -> Link {
    if t.is_none() {
        t = Some(Box::new(Node {
            cnt: 0,
            next: Default::default(),
        }));
    }
    let mut t = t.unwrap();
    if s.len() == 0 {
        t.cnt += 1;
    } else {
        let k = s[0];
        let next = t.next[k].take();
        t.next[k] = insert(next, &s[1..]);
    }
    Some(t)
}

fn convert(s: String) -> Vec<usize> {
    let mut a = Vec::with_capacity(s.len());
    for c in s.chars() {
        let k = c as usize - 'A' as usize;
        a.push(k);
    }
    a
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let s = convert(it.next().unwrap().to_string());
    let n: usize = it.next().unwrap().parse().unwrap();
    let mut t = None;
    for _ in 0..n {
        let a = convert(it.next().unwrap().to_string());
        t = insert(t, &a);
    }
    let mut ans = 0;
    for i in 0..s.len() {
        let mut now = &t;
        for &k in &s[i..] {
            now = &now.as_ref().unwrap().next[k];
            match now {
                None => break,
                Some(ref t) => {
                    ans += t.cnt;
                }
            }
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}
0