結果

問題 No.430 文字列検索
コンテスト
ユーザー srtry
提出日時 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

ソースコード

diff # 

/* 
 *     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();
}
0