結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 2 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

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