結果
問題 |
No.430 文字列検索
|
ユーザー |
|
提出日時 | 2025-09-27 12:21:54 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 783 ms / 2,000 ms |
コード長 | 1,791 bytes |
コンパイル時間 | 28,001 ms |
コンパイル使用メモリ | 397,788 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-27 12:23:05 |
合計ジャッジ時間 | 20,885 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
コンパイルメッセージ
warning: constant `pow26` should have an upper case name --> src/main.rs:11:7 | 11 | const pow26:[usize;10] = [ | ^^^^^ help: convert the identifier to upper case: `POW26` | = note: `#[warn(non_upper_case_globals)]` on by default
ソースコード
/* * Author: srtry * Created: 2025-09-23T00:46:59+09:00 * Coding: utf-8-unix */ use proconio::input; use proconio::marker::Chars; use std::{io::{stdout, BufWriter, Write}}; const pow26:[usize;10] = [ 1, 26, 676, 17576, 456976, 11881376, 308915776, 8031810176, 208827064576, 5429503678976 ]; fn my_hash(arg:&Vec<char>) -> usize { let mut hash_:usize = 0; for (i,&ch) in arg.iter().enumerate() { let tmp:usize = ((ch.clone() as u8) - b'A') as usize; hash_ += tmp * pow26[i]; } hash_ } fn main() { input!{ s:Chars, m:usize, c:[Chars;m] } let out = stdout(); let mut out = BufWriter::new(out.lock()); let mut roll_hashes:[usize;10] = [0;10]; for i in 1..=10 { if i<=s.len(){ let tmp:Vec<char> = (s[..i]).iter().cloned().collect::<Vec<char>>(); roll_hashes[i-1] = my_hash(&tmp); } } let mut ans:usize = 0; for c_elem in c.iter() { if c_elem.len() > s.len() { continue; } // 検索文字列のハッシュ計算 let c_hash:usize = my_hash(&c_elem); let mut roll_hash:usize = 26*roll_hashes[c_elem.len()-1]; let mut pre_top_hash:usize = 0; let mut last_hash:usize = 0; for i in 0..s.len()-c_elem.len()+1{ roll_hash = (roll_hash - pre_top_hash)/26 + (last_hash*pow26[c_elem.len()-1]); if roll_hash == c_hash { ans += 1; } pre_top_hash = ((s[i] as u8) - b'A') as usize; if i+c_elem.len() < s.len(){ last_hash = ((s[i+c_elem.len()] as u8) - b'A') as usize}; } } write!(out, "{}", ans).unwrap(); }