結果
問題 | No.430 文字列検索 |
ユーザー | zundamo-ti |
提出日時 | 2020-11-07 18:32:50 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,336 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 76,832 KB |
最終ジャッジ日時 | 2024-11-10 00:48:42 |
合計ジャッジ時間 | 5,590 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
59,556 KB |
testcase_01 | AC | 1,996 ms
76,832 KB |
testcase_02 | TLE | - |
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 | -- | - |
ソースコード
import sys read = sys.stdin.read readline = sys.stdin.readline readlines = sys.stdin.readlines class KMP(): def __init__(self, pattern): n = len(pattern) table = [0]*(n + 1) table[0], table[1] = -1, 0 i, j = 2, 0 while i <= n: if pattern[i - 1] == pattern[j]: table[i] = j + 1 i += 1; j += 1 elif j > 0: j = table[j] else: table[i] = 0 i += 1 self.size = n self.pattern = pattern self.table = table def search(self, text): l = len(text) n = self.size table = self.table pattern = self.pattern m, i = 0, 0 ret = 0 while m + i < l: if pattern[i] == text[m + i]: i += 1 if i == n: ret += 1 m += i - table[i] i = table[i] else: m += i - table[i] if i > 0: i = table[i] return ret def main(): S = readline().strip() N = int(readline()) ans = 0 for _ in range(N): kmp = KMP(readline().strip()) ans += kmp.search(S) print(ans) if __name__ == "__main__": main()