結果
問題 | No.2454 Former < Latter |
ユーザー |
![]() |
提出日時 | 2023-09-01 23:24:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 858 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 87,868 KB |
最終ジャッジ日時 | 2025-01-03 12:27:23 |
合計ジャッジ時間 | 3,420 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
import sysinput = sys.stdin.readlinedef Z_algorithm(s):n = len(s)A = [n] + [0] * (n-1)i, j = 1, 0while i < n:while i + j < n and s[j] == s[i+j]:j += 1A[i] = jif j == 0:i += 1continuek = 1while i + k < n and k + A[k] < j:A[i+k] = A[k]k += 1i += kj -= kreturn AT = int(input())for _ in range(T):N = int(input())S = list(input().rstrip())S = [ord(s) - ord("a") for s in S]L = Z_algorithm(S)ans = 0for i in range(1, N):L[i] = min(i, L[i])if i == L[i] and 2 * i < N:ans += 1else:if i + L[i] <= N - 1:if S[L[i]] < S[i + L[i]]:ans += 1print(ans)