結果
問題 | No.599 回文かい |
ユーザー |
![]() |
提出日時 | 2024-06-11 03:47:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,094 ms / 4,000 ms |
コード長 | 960 bytes |
コンパイル時間 | 931 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 100,224 KB |
最終ジャッジ日時 | 2025-01-03 08:35:49 |
合計ジャッジ時間 | 7,088 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
# Z algorithm# https://snuke.hatenablog.com/entry/2014/12/03/214243# 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を構築def z_algo(S):if len(S)==0:return []LEN=len(S)i=1j=0A=[0]*LENA[0]=LENwhile i<LEN:while i+j<LEN and S[j]==S[i+j]:j+=1A[i]=jif j==0:i+=1continuek=1while i+k<LEN and k+A[k]<j:A[i+k]=A[k]k+=1i+=kj-=kreturn Amod=10**9+7S=input().strip()DP=[0]*((len(S)+1)//2+1)DP[0]=1ANS=0for i in range((len(S))//2+1):A=z_algo(S[i:len(S)-i])#print(A)LIST=[]for j in range(len(A)-1):if A[len(A)-1-j]==j+1:LIST.append(j+1)#print("!",j+1)for l in LIST:if i+l<len(DP):DP[i+l]=(DP[i+l]+DP[i])%modANS=(ANS+DP[i])%modprint(ANS)