結果

問題 No.430 文字列検索
コンテスト
ユーザー Blue_S
提出日時 2024-02-01 21:00:21
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,338 bytes
コンパイル時間 13,329 ms
コンパイル使用メモリ 378,516 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 01:10:19
合計ジャッジ時間 17,887 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 RE * 1
other AC * 1 WA * 12 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        s: Bytes,
        m: usize,
        c: [Bytes; m],
    }


    let rh = RollingHash::build(s.clone());
    let mut crh = vec![];
    for i in 0..m {
        let tmp = RollingHash::build(c[i].clone());
        crh.push(tmp);
    }

    let mut ans = 0;

    for i in 0..m {
        let len = c[i].len();
        for j in 0..s.len() - len {
            if crh[i].get(0, c[i].len()) == rh.get(j, j + len) {
                ans += 1;
            }
        }
    } 

    println!("{ans}");
}



const MOD: usize = 999_999_937;
const BASE: usize = 3491;


#[allow(unused)]
struct RollingHash {
    s: Vec<u8>,
    prefix: Vec<usize>,
    power: Vec<usize>,
}

#[allow(unused)]
impl RollingHash {
    pub fn build(s: Vec<u8>) -> Self {
        let n = s.len();
        let mut prefix = vec![0; n + 1];
        let mut power = vec![1; n + 1];
        for i in 0..n {
            let c = (s[i] - b'a' + 1) as usize;
            prefix[i + 1] = (prefix[i] * BASE + c) % MOD;
            power[i + 1] = (power[i] * BASE) % MOD;
        }
        RollingHash {
            s: s,
            prefix: prefix,
            power: power,
        }
    }

    pub fn get(&self, l: usize, r: usize) -> usize {
        (self.prefix[r] - self.power[r - 1] * self.prefix[l]) % MOD
    }
}
0