結果
問題 |
No.2454 Former < Latter
|
ユーザー |
![]() |
提出日時 | 2023-09-02 02:12:21 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 853 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 78,592 KB |
最終ジャッジ日時 | 2024-06-11 08:51:08 |
合計ジャッジ時間 | 3,091 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 WA * 7 |
ソースコード
import sys input = sys.stdin.readline T=int(input()) for tests in range(T): N=int(input()) S=input().strip() # Z algorithm # https://snuke.hatenablog.com/entry/2014/12/03/214243 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 #print(A) ANS=0 for i in range(1,N): L=i R=N-i a=A[i] if a==R: if L<a: ANS+=1 continue if a==L: ANS+=1 continue if S[a]<S[i+a]: ANS+=1 print(ANS)