結果

問題 No.1005 BOT対策
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:21:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,936 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 81,256 KB
最終ジャッジ日時 2025-04-16 15:22:18
合計ジャッジ時間 2,753 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    S = sys.stdin.readline().strip()
    T = sys.stdin.readline().strip()
    
    len_S = len(S)
    len_T = len(T)
    
    if len_T == 0:
        print(0)
        return
    
    if len_T > len_S:
        print(0)
        return
    
    # Precompute failure function for T
    failure = [0] * len_T
    for i in range(1, len_T):
        j = failure[i-1]
        while j > 0 and T[i] != T[j]:
            j = failure[j-1]
        if T[i] == T[j]:
            j += 1
        failure[i] = j
    
    # Precompute transition table
    transition = [[0] * 26 for _ in range(len_T)]
    for j in range(len_T):
        for c_ord in range(26):
            c = chr(ord('a') + c_ord)
            current_j = j
            while True:
                if T[current_j] == c:
                    next_state = current_j + 1
                    break
                elif current_j == 0:
                    next_state = 0
                    break
                else:
                    current_j = failure[current_j - 1]
            transition[j][c_ord] = next_state
    
    # Initialize DP table
    INF = float('inf')
    dp = [[INF] * len_T for _ in range(len_S + 1)]
    dp[0][0] = 0
    
    for i in range(len_S):
        current_char = S[i]
        c_ord = ord(current_char) - ord('a')
        for j in range(len_T):
            if dp[i][j] == INF:
                continue
            # Option 1: Do not insert a dot here
            next_state = transition[j][c_ord]
            if next_state < len_T:
                if dp[i+1][next_state] > dp[i][j]:
                    dp[i+1][next_state] = dp[i][j]
            # Option 2: Insert a dot here
            new_count = dp[i][j] + 1
            if dp[i+1][0] > new_count:
                dp[i+1][0] = new_count
    
    min_dots = min(dp[len_S][j] for j in range(len_T))
    print(min_dots if min_dots != INF else -1)

if __name__ == "__main__":
    main()
0