結果
問題 | No.2454 Former < Latter |
ユーザー |
![]() |
提出日時 | 2023-09-02 02:16:04 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 853 bytes |
コンパイル時間 | 91 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 22,784 KB |
最終ジャッジ日時 | 2024-06-11 08:54:29 |
合計ジャッジ時間 | 10,895 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
import sysinput = sys.stdin.readlineT=int(input())for tests in range(T):N=int(input())S=input().strip()# Z algorithm# https://snuke.hatenablog.com/entry/2014/12/03/214243LEN=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-=k#print(A)ANS=0for i in range(1,N):L=iR=N-ia=A[i]if a==R:if L<a:ANS+=1continueif a>=L:ANS+=1continueif S[a]<S[i+a]:ANS+=1print(ANS)