結果

問題 No.2905 Nabeatsu Integration
ユーザー amentorimaru
提出日時 2024-06-04 11:50:55
言語 Ruby
(3.4.1)
結果
AC  
実行時間 897 ms / 2,000 ms
コード長 665 bytes
コンパイル時間 793 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-07 11:33:56
合計ジャッジ時間 40,176 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
  i = n - 1
  while i >= 0
    if a[i] + i >= n
      ans += add
      ans %= mod
    end
    add *= 10
    add %= mod
    i -= 1
  end

  puts ans
end

main if __FILE__ == $PROGRAM_NAME
0