結果

問題 No.430 文字列検索
コンテスト
ユーザー Igrmi
提出日時 2021-10-28 02:45:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 667 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 82,944 KB
最終ジャッジ日時 2024-11-10 00:57:57
合計ジャッジ時間 6,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 2 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

def getkmpnext(S):
    N = len(S)
    KMPNext = [-1] * (N + 1)
    j = -1
    for i in range(1, N + 1):
        while j >= 0 and S[i - 1] != S[j]: j = KMPNext[j]
        j += 1
        if i == N or S[i] != S[j]: KMPNext[i] = j
        else: KMPNext[i] = KMPNext[j]
    return KMPNext

def kmp(S, T):
    N = len(S)
    M = len(T)
    KMPNext = getkmpnext(T)
    j = 0
    Res = 0
    for i in range(N):
        while j != KMPNext[0] and S[i] != T[j]: j = KMPNext[j]
        j += 1
        if j == M:
            Res += 1
            j = KMPNext[j]
    return Res

S = input()
Q = int(input())
Ans = 0
for _ in range(Q):
    T = input()
    Ans += kmp(S, T)
print(Ans)
0