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

• 問題: No.430 文字列検索
• ユーザー: pianoneko
• 提出日時: 2019-09-24 04:25:52
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 181 ms / 2,000 ms
• コード長: 5,391 bytes
• コンパイル時間: 3,556 ms
• コンパイル使用メモリ: 197,060 KB
• 実行使用メモリ: 17,960 KB
• 最終ジャッジ日時: 2023-10-19 08:42:53
• 合計ジャッジ時間: 5,054 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,348 KB
testcase_01	AC	181 ms; 17,960 KB
testcase_02	AC	34 ms; 4,348 KB
testcase_03	AC	34 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	1 ms; 4,348 KB
testcase_08	AC	172 ms; 17,960 KB
testcase_09	AC	1 ms; 4,348 KB
testcase_10	AC	11 ms; 4,348 KB
testcase_11	AC	86 ms; 6,344 KB
testcase_12	AC	86 ms; 6,344 KB
testcase_13	AC	85 ms; 6,344 KB
testcase_14	AC	76 ms; 5,288 KB
testcase_15	AC	66 ms; 4,760 KB
testcase_16	AC	41 ms; 4,348 KB
testcase_17	AC	37 ms; 4,348 KB

コンパイルメッセージ

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

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

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

warning: static `MOD` is never used
   --> Main.rs:144:8
    |
144 | static MOD: i64 = 1_000_000_007;
    |        ^^^

warning: 4 warnings emitted

ソースコード

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 = 1_000_000_007;

struct RollingHash2 {
    rh1: RollingHash,
    rh2: RollingHash,
}

impl RollingHash2 {
    fn new(s: &Vec<i64>) -> Self {
        let (rh1, rh2) = RollingHash::create_recommended_pair(&s);
        RollingHash2 { rh1: rh1, rh2: rh2 }
    }
    fn get(&self, l: usize, r: usize) -> (i64, i64) {
        (self.rh1.get(l, r), self.rh2.get(l, r))
    }
}

struct RollingHash {
    modulo: i64,
    power: Vec<i64>,
    hash: Vec<i64>,
}

impl RollingHash {
    fn create_recommended_pair(s: &Vec<i64>) -> (Self, Self) {
        (
            RollingHash::new(&s, 1009, 1_000_000_007),
            RollingHash::new(&s, 1007, 1_000_000_009),
        )
    }
    fn new(s: &Vec<i64>, base: i64, modulo: i64) -> Self {
        let n = s.len();
        let mut power = vec![1; n + 1];
        let mut hash = vec![0; n + 1];

        for i in 0..n {
            power[i + 1] = power[i] * base % modulo;
            hash[i + 1] = (hash[i] * base + s[i]) % modulo;
        }

        RollingHash {
            modulo: modulo,
            power: power,
            hash: hash,
        }
    }

    fn get(&self, l: usize, r: usize) -> i64 {
        (self.hash[r] + self.modulo - (self.hash[l] * self.power[r - l]) % self.modulo)
            % self.modulo
    }
}

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

    for _ in 0..m {
        input!(c: String);
        let cvec: Vec<i64> = c.chars().map(|c| c as i64).collect();
        let crh = RollingHash2::new(&cvec);
        let h = crh.get(0, c.len());
        if map.contains_key(&h) {
            ans += map[&h];
        }
    }

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