#831641 (Crystal) No.430 文字列検索

提出ソース
結果

問題	No.430 文字列検索
コンテスト
ユーザー	ngng628
提出日時	2023-01-08 21:59:14
言語	Crystal (1.14.0)
結果	MLE
実行時間	-
コード長	8,467 bytes
コンパイル時間	11,781 ms
コンパイル使用メモリ	296,432 KB
実行使用メモリ	634,796 KB
最終ジャッジ日時	2024-11-10 01:03:51
合計ジャッジ時間	15,307 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	-- * 4
other	AC * 1 MLE * 1 -- * 12
権限があれば一括ダウンロードができます
ソースコード

raw source code
# ○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．
def int(b = 0); read_line.to_i64 + b end
def ints(b = 0); read_line.split.map{ |x| x.to_i64 + b } end
def str; read_line.chomp end
macro chmin(a, b); {{a}} = Math.min({{a}}, {{b}}) end
macro chmax(a, b); {{a}} = Math.max({{a}}, {{b}}) end
OO = (1_i64<<62)-(1_i64<<31)
# ○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．○。．

s = str
n = s.size
m = int
c = (1..m).map{ str }

rh = RollingHash.new(s)
cnts = Hash(UInt64, Int64).new(0_i64)
(1..n).each do |len|
  (n - len + 1).times do |i|
    hash = rh.substr(i, len)
    cnts[hash] += 1
  end
end

ans = c.sum{ |ci| cnts[rh.hash(ci)] }

puts ans



class RollingHash
  MOD = (1_u64 << 61) - 1 

  getter size : Int32
  @base : UInt64
  @power : Array(UInt64)
  @hash : Array(UInt64)

  # 配列 a に対する、基数が base のロリハを構築します。
  #
  # base は指定しない場合、ランダムに生成されます。
  #
  # ```
  # rh = RollingHash.new([1, 2, 5, 1, 2])
  # ```
  def initialize(a : Array(Int), base : UInt64? = nil)
    initialize(a.size, a, base)
  end

  # 文字列 s に対する、基数が base のロリハを構築します。
  #
  # base は指定しない場合、ランダムに生成されます。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # ```
  def initialize(s : String, base : UInt64? = nil )
    initialize(s.size, s.bytes, base)
  end

  # Enumerable な列 a に対する、基数が base のロリハを構築します。
  #
  # base は指定しない場合、ランダムに生成されます。
  #
  # ```
  # rh = RollingHash.new([1, 2, 5, 1, 2])
  # ```
  def initialize(@size, a : Enumerable, base : UInt64? = nil)
    base = RollingHash.create_base if base.nil?
    @base = base.not_nil!

    @power = [1_u64] * (@size + 1)
    @hash = [0_u64] * (@size + 1)

    a.each_with_index do |x, i|
      @power[i + 1] = mul(@power[i], @base)
      @hash[i + 1] = mul(@hash[i], @base) + x.to_u64
      @hash[i + 1] -= MOD if @hash[i + 1] >= MOD
    end
  end

  # ランダムに基底を生成します。
  #
  # ```
  # base = RollingHash.create_base
  # base # => 1729
  # ```
  def self.create_base
    rand(628_u64..MOD - 2)
  end

  # 文字列 s のハッシュを返します。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # rh.hash("is") # => 339225237399054811
  # rh.hash("abc") # => 496222201481864933
  # ```
  def hash(s : String)
    hash(s.bytes)
  end

  # 列 s のハッシュを返します。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # rh.hash("is") # => 339225237399054811
  # rh.hash("abc") # => 496222201481864933
  # ```
  def hash(s : Enumerable)
    s.reduce(0_u64){ |acc, ti| mul(acc, @base) + ti.to_u64 }
  end

  # s[start...start + length] のハッシュを返します。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # rh.substr(4, length: 2) # => 339225237399054811
  # rh.substr(5, length: 2) # => 339225237399054811
  # ```
  def substr(start : Int, length : Int) : UInt64
    res = @hash[start + length] + MOD - mul(@hash[start], @power[length])
    res < MOD ? res : res - MOD
  end

  # rangeで指定した範囲 s[l...r] のハッシュを返します。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # rh.slice(4..5) # => 339225237399054811
  # rh.slice(5..6) # => 339225237399054811
  # ```
  def slice(range : Range(Int?, Int?)) : UInt64
    left = (range.begin || 0)
    right = if range.end.nil?
        @size
      else
        range.end.not_nil! + (range.exclusive? ? 0 : 1)
      end
  
    length = right - left

    substr(start: left, length: length)
  end

  # rangeで指定した範囲 s[l...r] のハッシュを返します。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # rh[4..5] # => 339225237399054811
  # rh[5..6] # => 339225237399054811
  # ```
  def [](range : Range(Int?, Int?)) : UInt64
    slice(range)
  end

  # ハッシュ値 h1 とハッシュ値 h2 を結合したときのハッシュ値を返します。
  #
  # ハッシュ値 h2 の元々の長さを渡す必要があります。
  #
  # ```
  # rh = RollingHash.new("missisippi")
  # h1 = rh[1..2] # "is"
  # h2 = rh[5..6] # "si"
  # h = rh.concat(h1, h2, h2_len: 2)
  # h == rh.[1..4] # => true
  # ```
  def concat(h1 : UInt64, h2 : UInt64, h2_len : Int) : UInt64
    res = mul(h1, @power[h2_len]) + h2
    res < MOD ? res : res - MOD
  end

  # s[i...] と other[j...] の最長共通接頭辞の長さを返します。
  #
  # other はデフォルトで自分自身を渡しています。
  # 自分自身以外を渡す場合は (mod, base) が一致している必要があります。
  #
  # ```
  # rh1 = RollingHash.new("missisippi")
  # rh1 = rh1.lcp(3, 5) # => 2
  # rh1 = rh1.lcp(0, 1) # => 0
  # ```
  def lcp(i : Int, j : Int, other = self) : Int32
    length = Math.min(@hash.size - i, @hash.size - j)

    ok = length - (1..length).bsearch{ |len|
      l = length - len
      self.substr(start: i, length: l) == other.substr(start: j, length: l)
    }.not_nil!

    return ok.to_i32
  end

  # s[i...] と t[j...] の最長共通接頭辞の長さを返します。
  #
  # i, j はデフォルトで 0 を渡しています。
  #
  # ```
  # rh1 = RollingHash.new("missisippi", base: 628)
  # rh2 = RollingHash.new("thisisapen", base: 628)
  # RollingHash.lcp(rh1, rh2) # => 0
  # RollingHash.lcp(rh1, rh2, 4, 2) # => 3
  # ```
  def self.lcp(rh1 : self, rh2 : self, i : Int = 0, j : Int = 0) : Int32
    rh1.lcp(i, j, rh2)
  end

  # 文字列検索を行います。
  #
  # s[offset..] から t と一致する初めての添字を返します。
  # 添字は s が基準です。また、offset が加算された値が返ります。
  #
  # 存在しない場合は nil を返します。
  #
  # ```
  # rh = RollingHash.new("missisippi", base: 628)
  # rh.index("is") # => 1
  # rh.index("is", offset: 4) # => 4
  # rh.index("mid") # => nil
  # rh.index("i") # => 1
  # rh.index("pi") # => 8
  # ```
  def index(t : String, offset : Int = 0) : Int32?
    index(t.bytes, offset)
  end

  # 検索を行います。
  #
  # s[offset..] から t と一致する初めての添字を返します。
  # 添字は s が基準です。また、offset が加算された値が返ります。
  #
  # 存在しない場合は nil を返します。
  #
  # ```
  # rh = RollingHash.new("missisippi", base: 628)
  # rh.index("is") # => 1
  # rh.index("is", offset: 4) # => 4
  # rh.index("mid") # => nil
  # rh.index("i") # => 1
  # rh.index("pi") # => 8
  # ```
  def index(t : Enumerable, offset : Int = 0) : Int32?
    ths = hash(t)
    t_len = t.size
    res = (offset..@size - t.size).index{ |i| ths == substr(i, t_len) }
    res ? res.not_nil! + offset : nil
  end

  # 文字列検索を行います。
  #
  # s[offset..] から t と一致する初めての添字を返します。
  # 添字は s が基準です。また、offset が加算された値が返ります。
  #
  # 存在しない場合は例外を投げます。
  #
  # ```
  # rh = RollingHash.new("missisippi", base: 628)
  # rh.index!("is") # => 1
  # rh.index!("is", offset: 4) # => 4
  # rh.index!("mid") # => Enumerable::NotFoundError
  # rh.index!("i") # => 1
  # rh.index!("pi") # => 8
  # ```
  def index!(t : String, offset : Int = 0) : Int32
    index!(t.bytes, offset)
  end

  # 検索を行います。
  #
  # s[offset..] から t と一致する初めての添字を返します。
  # 添字は s が基準です。また、offset が加算された値が返ります。
  #21
  # 存在しない場合は例外を投げます。
  #
  # ```
  # rh = RollingHash.new("missisippi", base: 628)
  # rh.index!("is") # => 1
  # rh.index!("is", offset: 4) # => 4
  # rh.index!("mid") # => Enumerable::NotFoundError
  # rh.index!("i") # => 1
  # rh.index!("pi") # => 8
  # ```
  def index!(t : Enumerable, offset : Int = 0) : Int32
    ths = 0_u64
    t.each{ |ti| ths = mul(ths, @base) + ti.to_u64 }
    t_len = t.size
    (offset..@size - t.size).index!{ |i| ths == substr(i, t_len) } + offset
  end

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

結果

ソースコード
