結果

問題 No.430 文字列検索
ユーザー zundamo-tizundamo-ti
提出日時 2020-11-07 18:32:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,336 bytes
コンパイル時間 854 ms
コンパイル使用メモリ 87,116 KB
実行使用メモリ 77,908 KB
最終ジャッジ日時 2023-09-29 20:44:13
合計ジャッジ時間 7,619 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,200 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 # 

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()
0