test/string/rolling_hash_test.cr

• View this file on GitHub
• Last update: 2021-08-04 18:11:49+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B

Depends on

• src/string/rolling_hash.cr

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B
require "../../src/string/rolling_hash"
s = RollingHash.new read_line
t = RollingHash.new read_line
(0..s.size - t.size).each do |i|
  puts i if s[i, t.size] == t[0, t.size]
end

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B
# require "../../src/string/rolling_hash"
class RollingHash
  MOD = (1u64 << 61) - 1

  private def mul(a : UInt64, b : UInt64)
    t = a.to_u128 * b
    t = (t >> 61) + (t & MOD)
    (t < MOD ? t : t - MOD).to_u64
  end

  getter size : Int32

  def initialize(s : String, base : UInt64 = 10007u64)
    initialize(s.size, s.each_char, base, &.ord)
  end

  def initialize(a : Array(Int), base : UInt64 = 10007u64)
    initialize(a.size, a, base, &.itself)
  end

  def initialize(@size, a : Enumerable, base : UInt64 = 10007u64, &)
    @pow = Array(UInt64).new(size + 1, 1)
    @hash = Array(UInt64).new(size + 1, 0)
    a.each_with_index do |x, i|
      @pow[i + 1] = mul(@pow[i], base)
      @hash[i + 1] = mul(@hash[i], base) + yield(x)
      @hash[i + 1] -= MOD if @hash[i + 1] >= MOD
    end
  end

  def [](start : Int, count : Int) : UInt64
    res = @hash[start + count] + MOD - mul(@hash[start], @pow[count])
    res < MOD ? res : res - MOD
  end

  def [](range : Range) : UInt64
    self[*Indexable.range_to_index_and_count(range, size) || raise IndexError.new]
  end
end

s = RollingHash.new read_line
t = RollingHash.new read_line
(0..s.size - t.size).each do |i|
  puts i if s[i, t.size] == t[0, t.size]
end

Back to top page