結果

問題 No.2454 Former < Latter
コンテスト
ユーザー keiden
提出日時 2024-09-23 01:18:44
言語 Scheme
(Gauche-0.9.15)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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