結果

問題 No.430 文字列検索
ユーザー hatoo
提出日時 2019-05-16 00:00:09
言語 Rust
(1.30.1)
結果
AC  
実行時間 42 ms
コード長 4,671 Byte
コンパイル時間 2,579 ms
使用メモリ 9,128 KB
最終ジャッジ日時 2019-05-16 00:00:13

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 4 ms
9,096 KB
challenge02.txt AC 42 ms
9,124 KB
challenge03.txt AC 32 ms
9,120 KB
challenge04.txt AC 31 ms
9,120 KB
sample1.txt AC 5 ms
9,096 KB
sample2.txt AC 5 ms
9,096 KB
sample3.txt AC 5 ms
9,100 KB
sample4.txt AC 5 ms
9,100 KB
test1.txt AC 37 ms
9,116 KB
test2.txt AC 5 ms
9,112 KB
test3.txt AC 9 ms
9,116 KB
test4.txt AC 41 ms
9,124 KB
test5.txt AC 42 ms
9,128 KB
test6.txt AC 41 ms
9,120 KB
test7.txt AC 39 ms
9,120 KB
test8.txt AC 37 ms
9,120 KB
test9.txt AC 35 ms
9,120 KB
test10.txt AC 33 ms
9,120 KB
テストケース一括ダウンロード

ソースコード

diff #
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
mod util {
    use std::fmt::Debug;
    use std::io::{stdin, stdout, BufWriter, StdoutLock};
    use std::str::FromStr;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn chars() -> Vec<char> {
        line().chars().collect()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
    #[allow(dead_code)]
    pub fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
        let out = stdout();
        let writer = BufWriter::new(out.lock());
        f(writer)
    }
}
#[allow(unused_macros)]
macro_rules ! get { ( [ $ t : ty ] ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( [ $ t : ty ] ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( [ $ t ] ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

use std::default::Default;
use std::hash::{BuildHasherDefault, Hasher};
#[doc = " An implementation of the Fowler\u{2013}Noll\u{2013}Vo hash function."]
#[doc = ""]
#[doc = " See the [crate documentation](index.html) for more details."]
#[doc = " Ported from [servo/rust-fnv](https://raw.githubusercontent.com/servo/rust-fnv/master/lib.rs)"]
#[allow(missing_copy_implementations)]
pub struct FnvHasher(u64);
impl Default for FnvHasher {
    #[inline]
    fn default() -> FnvHasher {
        FnvHasher(0xcbf29ce484222325)
    }
}
impl FnvHasher {
    #[doc = " Create an FNV hasher starting with a state corresponding"]
    #[doc = " to the hash `key`."]
    #[inline]
    pub fn with_key(key: u64) -> FnvHasher {
        FnvHasher(key)
    }
}
impl Hasher for FnvHasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let FnvHasher(mut hash) = *self;
        for byte in bytes.iter() {
            hash = hash ^ (*byte as u64);
            hash = hash.wrapping_mul(0x100000001b3);
        }
        *self = FnvHasher(hash);
    }
}
#[doc = " A builder for default FNV hashers."]
pub type FnvBuildHasher = BuildHasherDefault<FnvHasher>;
#[doc = " A `HashMap` using a default FNV hasher."]
pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;
#[doc = " A `HashSet` using a default FNV hasher."]
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;

fn solve() {
    let s = util::chars();
    let m = get!(usize);
    let c = get!(String; m);

    let set: FnvHashSet<String> = c.into_iter().collect();

    let mut ans = 0;
    for i in 1..=10 {
        for w in s.windows(i) {
            let s = w.iter().collect::<String>();
            if set.contains(&s) {
                ans += 1;
            }
        }
    }

    println!("{}", ans);
}
0