結果
問題 | 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=1 j=0 A=[0]*LEN A[0]=LEN while i<LEN: while i+j<LEN and S[j]==S[i+j]: j+=1 A[i]=j if j==0: i+=1 continue k=1 while i+k<LEN and k+A[k]<j: A[i+k]=A[k] k+=1 i+=k j-=k return A mod=10**9+7 S=input().strip() DP=[0]*((len(S)+1)//2+1) DP[0]=1 ANS=0 for 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])%mod ANS=(ANS+DP[i])%mod print(ANS)