結果

問題 No.430 文字列検索
コンテスト
ユーザー qqqqq
提出日時 2019-07-28 21:18:40
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 981 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 203 ms
コンパイル使用メモリ 84,988 KB
実行使用メモリ 89,824 KB
最終ジャッジ日時 2026-05-09 09:56:47
合計ジャッジ時間 5,875 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 2 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class KMP():
    def __init__(self, pattern):
        self.pattern = pattern + "."
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        pattern = self.pattern
        j = -1
        for i in range(self.n):
            while j >= 0 and pattern[i] != pattern[j]:
                j = table[j]
            j += 1
            #table[i+1] = j
            if (pattern[i + 1] == pattern[j]):
                table[i + 1] = table[j]
            else:
                table[i + 1] = j
        self.table = table

    def match(self, s):
        i, j, n, m = 0,0,self.n,len(s)
        ret = 0
        for i in range(m):
            while j >= 0 and s[i] != self.pattern[j]:
                j = self.table[j]
            j += 1
            if j == n:
                ret += 1
        return ret

s = input()
m = int(input())
ans = 0
for i in range(m):
    t = input()
    kmp = KMP(t)
    ans += kmp.match(s)
print(ans)
0