#382645 (Rust) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: pianoneko
• 提出日時: 2019-09-23 17:36:24
• 言語: Rust (1.77.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 5,357 bytes
• コンパイル時間: 11,608 ms
• コンパイル使用メモリ: 378,792 KB
• 実行使用メモリ: 14,464 KB
• 最終ジャッジ日時: 2024-11-10 00:34:00
• 合計ジャッジ時間: 13,110 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	WA	-
testcase_02	AC	28 ms; 5,248 KB
testcase_03	AC	29 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	115 ms; 14,336 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	9 ms; 5,248 KB
testcase_11	AC	69 ms; 5,760 KB
testcase_12	AC	70 ms; 5,632 KB
testcase_13	WA	-
testcase_14	AC	62 ms; 5,248 KB
testcase_15	AC	55 ms; 5,248 KB
testcase_16	AC	33 ms; 5,248 KB
testcase_17	AC	32 ms; 5,248 KB

コンパイルメッセージ

warning: unused import: `std::io::BufRead`
 --> src/main.rs:2:5
  |
2 | use std::io::BufRead;
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `Add`, `Div`, `Mul`, `Sub`
 --> src/main.rs:4:16
  |
4 | use std::ops::{Add, Div, Mul, Sub};
  |                ^^^  ^^^  ^^^  ^^^

warning: variable does not need to be mutable
   --> src/main.rs:201:13
    |
201 |         let mut cvec: Vec<i64> = c.chars().map(|c| c as i64).collect();
    |             ----^^^^
    |             |
    |             help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: function `read` is never used
  --> src/main.rs:22:4
   |
22 | fn read<T: FromStr>() -> T {
   |    ^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: static `MOD` is never used
   --> src/main.rs:144:8
    |
144 | static MOD: i64 = 1e9 as i64 + 7;
    |        ^^^

warning: variable `S` should have a snake case name
   --> src/main.rs:185:12
    |
185 |     input!(S: String, M: usize);
    |            ^ help: convert the identifier to snake case (notice the capitalization): `s`
    |
    = note: `#[warn(non_snake_case)]` on by default

warning: variable `M` should have a snake case name
   --> src/main.rs:185:23
    |
185 |     input!(S: String, M: usize);
    |                       ^ help: convert the identifier to snake case: `m`

ソースコード

use std::fmt::Debug;
use std::io::BufRead;
use std::io::{stdin, Read};
use std::ops::{Add, Div, Mul, Sub};
use std::str::FromStr;

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

macro_rules! read {
    (($($t:tt),*)) => {
        ( $(read!($t)),* )
    };
    ([[$t:tt; $len1:expr]; $len2:expr]) => {
        (0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()
    };

    ([$t:tt; $len:expr]) => {
        (0..$len).map(|_| read!($t)).collect::<Vec<_>>()
    };

    (chars) => {
        read!(String).chars().collect::<Vec<char>>()
    };

    (usize1) => {
        read!(usize) - 1
    };

    ($t:ty) => {{
        let stdin = stdin();
        let stdin = stdin.lock();
        let token: String = stdin
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        token.parse::<$t>().unwrap()
    }};
}

macro_rules! input {
    (mut $name:ident: $t:tt, $($r:tt)*) => {
        let mut $name = read!($t);
        input!($($r)*);
    };

    (mut $name:ident: $t:tt) => {
        let mut $name = read!($t);
    };

    ($name:ident: $t:tt, $($r:tt)*) => {
        let $name = read!($t);
        input!($($r)*);
    };

    ($name:ident: $t:tt) => {
        let $name = read!($t);
    };
}

trait VecExt {
    fn cumulation(&self) -> Vec<i64>;
    fn cumulation_query(&self, a: &usize, b: &usize) -> i64;
}

impl VecExt for Vec<i64> {
    fn cumulation(&self) -> Vec<i64> {
        let mut vec = vec![0; self.len() + 1];
        for i in 0..self.len() {
            vec[i + 1] = self[i] + vec[i];
        }
        return vec;
    }

    fn cumulation_query(&self, left: &usize, right: &usize) -> i64 {
        return self[*right] - self[*left];
    }
}

trait SliceExt<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> SliceExt<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut ng = -1;
        let mut ok = self.len() as i64;

        while (ok - ng).abs() > 1 {
            let mid = (ok + ng) / 2;
            if self[mid as usize] >= *x {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok as usize;
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut ng = -1;
        let mut ok = self.len() as i64;
        while (ok - ng).abs() > 1 {
            let mid = (ok + ng) / 2;
            if self[mid as usize] > *x {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok as usize;
    }
}

static MOD: i64 = 1e9 as i64 + 7;

pub struct RollingHash {
    hash_pow_list: Vec<(i64, Vec<(i64, i64)>)>,
}
impl RollingHash {
    pub fn new(s: &[i64]) -> RollingHash {
        RollingHash::with_base_mod_pairs(s, &[(1009, 1_000_000_007), (9973, 999_999_937)])
    }
    pub fn with_base_mod_pairs(s: &[i64], base_mod_pairs: &[(i64, i64)]) -> RollingHash {
        let hp_list = base_mod_pairs
            .iter()
            .map(|&(base, m)| {
                let mut hp = Vec::with_capacity(s.len() + 1);
                hp.push((0, 1));
                for (i, &x) in s.iter().enumerate() {
                    let (h, p) = hp[i];
                    hp.push(((h + x) * base % m, p * base % m));
                }
                (m, hp)
            })
            .collect();
        RollingHash {
            hash_pow_list: hp_list,
        }
    }
    pub fn get(&self, l: usize, r: usize) -> i64 {
        self.hash_pow_list
            .iter()
            .map(|(m, hp)| (hp[r].0 + m - hp[l].0 * hp[r - l].1 % m) % m)
            .fold(0, |a, b| a ^ b)
    }
    pub fn len(&self) -> usize {
        self.hash_pow_list
            .first()
            .map(|v| v.1.len() - 1)
            .unwrap_or(0)
    }
}

fn main() {
    input!(S: String, M: usize);
    use std::collections::BTreeMap;
    let mut map: BTreeMap<i64, usize> = BTreeMap::new();
    let tmp: Vec<i64> = S.chars().map(|c| c as i64).collect();
    let rh = RollingHash::new(&tmp);
    let mut ans = 0;
    for i in 0..S.len() {
        for j in 0..std::cmp::min(10, S.len() - i) {
            let hash = rh.get(i, i + j + 1);
            let count = map.entry(hash).or_insert(0);
            *count += 1;
        }
    }

    for _ in 0..M {
        input!(c: String);
        let mut cvec: Vec<i64> = c.chars().map(|c| c as i64).collect();
        let crh = RollingHash::new(&cvec);
        match map.get(&crh.get(0, c.len())) {
            Some(&x) => {
                ans += x;
            }
            _ => (),
        };
    }

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