結果
問題 | No.430 文字列検索 |
ユーザー | HAMASHITA |
提出日時 | 2022-04-19 22:39:07 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,296 bytes |
コンパイル時間 | 86 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 16,384 KB |
最終ジャッジ日時 | 2024-11-10 00:59:48 |
合計ジャッジ時間 | 3,485 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
16,128 KB |
testcase_01 | TLE | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
ソースコード
alphabet_to_int = { 'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7, 'H': 8, 'I': 9, 'J': 10, 'K': 11, 'L': 12, 'M': 13, 'N': 14, 'O': 15, 'P': 16, 'Q': 17, 'R': 18, 'S': 19, 'T': 20, 'U': 21, 'V': 22, 'W': 23, 'X': 24, 'Y': 25, 'Z': 26 } def count_string(s: str, t: str): """ Rolling hash function """ count = 0 n = len(s) m = len(t) if n < m: return 0 base = 26 mod = 10 ** 9 + 7 t_hash = 0 for i, c in enumerate(t): t_hash += alphabet_to_int[c] * (base ** (m - i - 1)) t_hash %= mod s_hash = 0 for i in range(m): s_hash += alphabet_to_int[s[i]] * (base ** (m - i - 1)) s_hash %= mod if s_hash == t_hash: count += 1 # rolling hash for i in range(1, len(s) - m + 1): s_hash = s_hash * base - alphabet_to_int[s[i - 1]] * (base ** m) + alphabet_to_int[s[i + m - 1]] s_hash %= mod if s_hash == t_hash: count += 1 return count if __name__ == "__main__": s = str(input()) m = int(input()) t_array = [str(input()) for _ in range(m)] result = 0 for t in t_array: result += count_string(s, t) print(result)