結果

問題 No.430 文字列検索
ユーザー akakimidoriakakimidori
提出日時 2019-10-05 02:13:11
言語 Rust
(1.77.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,449 bytes
コンパイル時間 853 ms
コンパイル使用メモリ 160,060 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-15 00:31:12
合計ジャッジ時間 1,646 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 10 ms
6,940 KB
testcase_02 AC 4 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 9 ms
6,944 KB
testcase_12 AC 10 ms
6,940 KB
testcase_13 AC 10 ms
6,940 KB
testcase_14 AC 8 ms
6,940 KB
testcase_15 AC 6 ms
6,940 KB
testcase_16 AC 6 ms
6,940 KB
testcase_17 AC 6 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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