結果

問題 No.430 文字列検索
コンテスト
ユーザー Koutaro Miura
提出日時 2022-07-10 22:22:49
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,001 bytes
コンパイル時間 10,904 ms
コンパイル使用メモリ 407,448 KB
実行使用メモリ 9,380 KB
最終ジャッジ日時 2024-11-10 01:01:34
合計ジャッジ時間 14,492 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `S` should have a snake case name
 --> src/main.rs:6:9
  |
6 |         S: Chars,
  |         ^ 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:7:9
  |
7 |         M: usize,
  |         ^ help: convert the identifier to snake case: `m`

warning: variable `C` should have a snake case name
 --> src/main.rs:8:9
  |
8 |         C: [String; M]
  |         ^ help: convert the identifier to snake case (notice the capitalization): `c`

ソースコード

diff # 

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

// 430
fn main() {
    input! {
        S: Chars,
        M: usize,
        C: [String; M]
    };

    let mut cnt = 0;
    for i in 0..M {
        if S.len() < C[i].len() { continue; }
        for j in 0..=(S.len() - C[i].len()) {
            if contain(&C[i], &S[j..(j + C[i].len())].iter().collect::<String>()) {
                cnt += 1;
            }
        }
    }
    println!("{}", cnt);
}

fn contain(a: &String, b: &String) -> bool {
    const B: u64 = 1000000007; let a = a.as_bytes(); let b = b.as_bytes(); let al = a.len(); let bl = b.len(); if al > bl { return false; } let mut ah = 0u64; let mut bh = 0u64; for i in 0..al { ah = ah.wrapping_mul(B).wrapping_add(a[i] as u64); bh = bh.wrapping_mul(B).wrapping_add(b[i] as u64); } let t = B.wrapping_pow(al as u32); for i in 0..=(bl - al) { if ah == bh { return true; } if i + al < bl { bh = bh.wrapping_mul(B).wrapping_add(b[i + al] as u64).wrapping_sub((b[i] as u64).wrapping_mul(t)); } } false
}
0