結果

問題 No.430 文字列検索
ユーザー qqqqqqqqqq
提出日時 2019-07-28 21:18:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 981 bytes
コンパイル時間 495 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 84,476 KB
最終ジャッジ日時 2024-11-10 00:26:51
合計ジャッジ時間 6,873 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
58,912 KB
testcase_01 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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