#1196315 (Fix) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: 👑 tttmmmyyyy
• 提出日時: 2026-10-31 23:36:09
• 言語: Fix (1.6.0 + cp-library + minilib)
• 結果: AC
• 実行時間: 27 ms / 2,000 ms
• コード長: 4,027 bytes
• コンパイル時間: 14,291 ms
• コンパイル使用メモリ: 672,284 KB
• 実行使用メモリ: 34,088 KB
• 最終ジャッジ日時: 2026-10-31 23:36:30
• 合計ジャッジ時間: 17,022 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

ファイルパターン	結果
sample	AC * 4
other	AC * 18

コンパイルメッセージ

make: 'lib.o' は更新済みです.

ソースコード

module Main;

import CPLib.IO;
import CPLib.ZP;
import HashMap::{empty, find, find_or, insert};

namespace RollingHash {
    __RHB : U64 = 1447220154650436572_U64;
    __RHBI : U64 = 2209944978905739324_U64;
    __RHM : U64 = 1_U64.shift_left(61_U64) - 1_U64;

    _mul_mod_m : U64 -> U64 -> U64 = |a, b| (
        let t = a.u128 * b.u128;
        let r = t.shift_right(61_U128).u64 + t.u64.bit_and(__RHM);
        let r = if r >= __RHM { r - __RHM } else { r };
        r
    );

    _add_mod_m : U64 -> U64 -> U64 = |a, b| (
        let r = a + b;
        let r = if r >= __RHM { r - __RHM } else { r };
        r
    );

    _neg_mod_m : U64 -> U64 = |a| (
        if a == 0_U64 { 0_U64 };
        __RHM - a
    );
    
    type RollingHash = struct {
        str : String,
        begin : I64,
        end : I64,
        hash : U64,
        power : U64 // b^(end-begin)
    };

    rolling_hash : String -> I64 -> I64 -> RollingHash = |str, begin, end| (
        if !(0 <= begin && begin <= end && end <= str.@size) {
            undefined("[RollingHash::rolling_hash] Invalid argument.")
        };
        let (power, hash) = range(begin, end).fold((1_U64, 0_U64), |i, (power, hash)|
            let byte = str[i].iget.u64;
            let hash = hash._add_mod_m(byte._mul_mod_m(power));
            let power = power._mul_mod_m(__RHB);
            (power, hash)
        );
        RollingHash { str, begin, end, hash, power }
    );

    push_back : RollingHash -> RollingHash = |RollingHash { str, begin, end, hash, power }| (
        if end >= str.@size {
            undefined("[RollingHash::push_back] end >= size.")
        };
        let byte = str[end].iget.u64;
        let hash = hash._add_mod_m(byte._mul_mod_m(power));
        let power = power._mul_mod_m(__RHB);
        let end = end + 1;
        RollingHash { str, begin, end, hash, power }
    );

    pop_back : RollingHash -> RollingHash = |RollingHash { str, begin, end, hash, power }| (
        if end <= begin {
            undefined("[RollingHash::pop_back] called for empty.")
        };
        let power = power._mul_mod_m(__RHBI);
        let end = end - 1;
        let byte = str[end].iget.u64;
        let hash = hash._add_mod_m(byte._mul_mod_m(power)._neg_mod_m);
        RollingHash { str, begin, end, hash, power }
    );

    push_front : RollingHash -> RollingHash = |RollingHash { str, begin, end, hash, power }| (
        if begin <= 0 {
            undefined("[RollingHash::push_front] begin <= 0.")
        };
        let begin = begin - 1;
        let byte = str[begin].iget.u64;
        let hash = hash._mul_mod_m(__RHB)._add_mod_m(byte);
        let power = power._mul_mod_m(__RHB);
        RollingHash { str, begin, end, hash, power }
    );

    pop_front : RollingHash -> RollingHash = |RollingHash { str, begin, end, hash, power }| (
        if begin >= end {
            undefined("[RollingHash::pop_front] called for empty.")
        };
        let byte = str[begin].iget.u64;
        let hash = hash._add_mod_m(byte._neg_mod_m)._mul_mod_m(__RHBI);
        let begin = begin + 1;
        let power = power._mul_mod_m(__RHBI);
        RollingHash { str, begin, end, hash, power }
    );
}

main : IO () = (
    let s = *read_s;
    let m = *read_i;
    let mp = HashMap::empty(5e5);
    let mp = range(1, 10.min(s.@size) + 1).fold(mp, |len, mp|
        // rolling_hash : String -> I64 -> I64 -> RollingHash = |str, begin, end| (
        let rh = rolling_hash(s, 0, len);
        range(0, s.@size - len + 1).fold((mp, rh), |begin, (mp, rh)|
            let h = rh.@hash;
            let v = mp.find_or(h, 0) + 1;
            let mp = mp.insert(h, v);
            let rh = if begin + len == s.@size { rh } else { rh.RollingHash::push_back.pop_front };
            (mp, rh)
        ).@0
    );
    let ans = *range(0, m).fold_m(0, |_, ans|
        let c = *read_s;
        let hash = rolling_hash(c, 0, c.@size).@hash;
        let ans = ans + mp.find_or(hash, 0);
        ans.pure
    );
    ans.to_string.println;;
    pure()
);