結果

問題 No.599 回文かい
ユーザー lam6er
提出日時 2025-04-16 16:22:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 853 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 81,788 KB
実行使用メモリ 66,264 KB
最終ジャッジ日時 2025-04-16 16:23:51
合計ジャッジ時間 2,811 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

S = input().strip()
n = len(S)

if n == 0:
    print(0)
    exit()

# Compute the failure function using KMP algorithm
f = [0] * n
for i in range(1, n):
    j = f[i-1]
    while j > 0 and S[i] != S[j]:
        j = f[j-1]
    if S[i] == S[j]:
        j += 1
    f[i] = j

# Initialize dp array where dp[i] represents the number of valid splits for the first i characters
dp = [0] * (n + 1)
dp[0] = 0  # empty string has no valid splits

for i in range(1, n + 1):
    dp[i] = 1  # split into one part is always valid
    # Check all possible l's from the failure function chain
    j = f[i-1] if i-1 >= 0 else 0
    while j > 0:
        if j <= i // 2:
            dp[i] += dp[i - 2 * j]
            dp[i] %= MOD
        # Move to the next possible l in the chain
        j = f[j-1] if j-1 >= 0 else 0
    dp[i] %= MOD

print(dp[n] % MOD)
0