結果

問題 No.2905 Nabeatsu Integration
ユーザー 👑 amentorimaru
提出日時 2024-06-04 11:40:24
言語 Ruby
(3.4.1)
結果
AC  
実行時間 976 ms / 2,000 ms
コード長 654 bytes
コンパイル時間 699 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-07 11:33:13
合計ジャッジ時間 43,984 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def z_algorithm(s)
  a = Array.new(s.length, 0)
  a[0] = s.length
  i = 1
  j = 0

  while i < s.length
    while i + j < s.length && s[j] == s[i + j]
      j += 1
    end
    a[i] = j
    if j == 0
      i += 1
      next
    end

    k = 1
    while i + k < s.length && k + a[k] < j
      a[i + k] = a[k]
      k += 1
    end

    i += k
    j -= k
  end

  a
end

def main
  s = gets.strip
  n = s.length
  a = z_algorithm(s)
  mod = 998244353
  ans = mod - n + 1
  add = 10
  (n - 1).downto(0) do |i|
    if a[i] + i >= n
      ans += add
      ans %= mod
    end
    add *= 10
    add %= mod
  end

  puts ans
end

main if __FILE__ == $PROGRAM_NAME
0