結果

問題 No.2454 Former < Latter
ユーザー keidenkeiden
提出日時 2024-09-23 01:18:44
言語 Scheme
(Gauche-0.9.14)
結果
AC  
実行時間 533 ms / 2,000 ms
コード長 1,149 bytes
コンパイル時間 36 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 20,736 KB
最終ジャッジ日時 2024-09-23 01:18:51
合計ジャッジ時間 6,341 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
16,256 KB
testcase_01 AC 26 ms
16,256 KB
testcase_02 AC 263 ms
19,568 KB
testcase_03 AC 159 ms
19,328 KB
testcase_04 AC 282 ms
19,456 KB
testcase_05 AC 258 ms
19,456 KB
testcase_06 AC 261 ms
19,200 KB
testcase_07 AC 274 ms
19,200 KB
testcase_08 AC 216 ms
19,584 KB
testcase_09 AC 143 ms
18,304 KB
testcase_10 AC 177 ms
17,792 KB
testcase_11 AC 231 ms
20,080 KB
testcase_12 AC 231 ms
19,128 KB
testcase_13 AC 231 ms
19,188 KB
testcase_14 AC 236 ms
19,568 KB
testcase_15 AC 197 ms
18,432 KB
testcase_16 AC 198 ms
18,816 KB
testcase_17 AC 533 ms
20,736 KB
testcase_18 AC 207 ms
20,224 KB
testcase_19 AC 199 ms
19,328 KB
testcase_20 AC 249 ms
19,456 KB
testcase_21 AC 252 ms
19,840 KB
testcase_22 AC 165 ms
17,664 KB
testcase_23 AC 168 ms
18,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

(define (z-algorithm s)
  (let*
    ((n (string-length s)) (z (make-vector n 0)) (l 0) (r 0))
    (vector-set! z 0 n)
    (do
      ((i 1 (+ i 1)))
      ((= i n) z)
      (when (<= i r)
        (if (< (- (+ r 1) i) (vector-ref z (- i l)))
          (vector-set! z i (- (+ r 1) i))
          (vector-set! z i (vector-ref z (- i l)))))
      (while (and (< (+ i (vector-ref z i)) n) (equal? (string-ref s (vector-ref z i)) (string-ref s (+ i (vector-ref z i)))))
        (vector-set! z i (+ 1 (vector-ref z i))))
      (when (< r (+ (- i 1) (vector-ref z i)))
        (set! l i)
        (set! r (+ (- i 1) (vector-ref z i)))))))


(define yuki2454
  (let*
    ((t (read)) (_ (read-line)))
    (dotimes (t)
      (let*
        ((n (read)) (_ (read-line)) (s (read-line)) (z (z-algorithm s)) (a 0))
        (do
          ((i 1 (+ i 1)))
          ((= i n))
          (let ((y (vector-ref z i)))
            (cond
              ((< i y)
                (set! a (+ a 1)))
              ((and (< (+ i y) n) (or (equal? i y) (char<? (string-ref s y) (string-ref s (+ i y)))))
                (set! a (+ a 1)))
              (else))))
        (print a)))))
0