結果
問題 | No.430 文字列検索 |
ユーザー | henoc on demand |
提出日時 | 2019-05-05 11:29:43 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 1,682 ms / 2,000 ms |
コード長 | 1,671 bytes |
コンパイル時間 | 12,690 ms |
コンパイル使用メモリ | 382,796 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-10 00:25:15 |
合計ジャッジ時間 | 28,887 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1,682 ms
5,248 KB |
testcase_02 | AC | 1,663 ms
5,248 KB |
testcase_03 | AC | 1,659 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 | 7 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | AC | 1,662 ms
5,248 KB |
testcase_12 | AC | 1,652 ms
5,248 KB |
testcase_13 | AC | 1,653 ms
5,248 KB |
testcase_14 | AC | 1,668 ms
5,248 KB |
testcase_15 | AC | 1,663 ms
5,248 KB |
testcase_16 | AC | 1,662 ms
5,248 KB |
testcase_17 | AC | 1,665 ms
5,248 KB |
コンパイルメッセージ
warning: unnecessary trailing semicolon --> src/main.rs:2:103 | 2 | macro_rules ! for_ { ( $ init : stmt ; $ cond : expr ; $ incr : expr , $ body : block ) => ( { $ init ; while $ cond { $ body $ incr ; } ... | ^ help: remove this semicolon ... 45 | / for_!(let mut i = 0; i + key_len <= base_len; i += 1, { 46 | | if key_h == base_h {ret.push(i);} 47 | | if i + key_len < base_len { 48 | | let p = base_h * B; ... | 54 | | } 55 | | }); | |______- in this macro invocation | = note: `#[warn(redundant_semicolons)]` on by default = note: this warning originates in the macro `for_` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
#[allow(unused_macros)] macro_rules ! for_ { ( $ init : stmt ; $ cond : expr ; $ incr : expr , $ body : block ) => ( { $ init ; while $ cond { $ body $ incr ; } } ) ; } fn main() { use std::io::Read; let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let s: String = iter.next().unwrap().parse::<String>().unwrap(); let m: usize = iter.next().unwrap().parse::<usize>().unwrap(); let mut cnt = 0; for _ in 0..m { let c: String = iter.next().unwrap().parse::<String>().unwrap(); cnt += search_rh(s.as_bytes(), c.as_bytes()).len(); } println!("{}", cnt); } #[doc = " O(len(base) + len(key))"] #[allow(dead_code)] pub fn search_rh(base: &[u8], key: &[u8]) -> Vec<usize> { const B: i64 = 9973; const M: i64 = 1_000_000_007; let key_len = key.len(); let base_len = base.len(); if key_len > base_len { return vec![]; } let mut t = 1i64; for _ in 0..key_len { t *= B; t %= M; } let mut key_h = 0; let mut base_h = 0; for i in 0..key_len { key_h = ((key_h * B) % M + (key[i] as i64) % M) % M; base_h = ((base_h * B) % M + (base[i] as i64) % M) % M; } let mut ret = vec![]; for_!(let mut i = 0; i + key_len <= base_len; i += 1, { if key_h == base_h {ret.push(i);} if i + key_len < base_len { let p = base_h * B; let q = base[i + key_len] as i64; let r = base[i] as i64 * t; let mut z = (p + q - r) % M; if z < 0 {z += M;} base_h = z; } }); ret }