NgLib::RollingHash

配列 $a$ に対する、基数が base のロリハを構築します。

base は指定しない場合、ランダムに生成されます。

rh = RollingHash.new([1, 2, 5, 1, 2])

文字列 $s$ に対する、基数が base のロリハを構築します。

base は指定しない場合、ランダムに生成されます。

rh = RollingHash.new("missisippi")

Enumerable な列 $a$ に対する、基数が base のロリハを構築します。

base は指定しない場合、ランダムに生成されます。

rh = RollingHash.new(5, [1, 2, 5, 1, 2])

ランダムに基底を生成します。

base = RollingHash.create_base
base # => 1729

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

range で指定した範囲 s[range] のハッシュを返します。

rh = RollingHash.new("missisippi")
rh[4..5] # => 339225237399054811
rh[5..6] # => 339225237399054811

ハッシュ値 $h_1$ とハッシュ値 $h_2$ を結合したときのハッシュ値を返します。

ハッシュ値 $h_2$ の元々の長さを渡す必要があります。

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

文字列 $s$ のハッシュを返します。

rh = RollingHash.new("missisippi")
rh.hash("is")  # => 339225237399054811
rh.hash("abc") # => 496222201481864933

列 $s$ のハッシュを返します。

rh = RollingHash.new("missisippi")
rh.hash("is")  # => 339225237399054811
rh.hash("abc") # => 496222201481864933

初期化時に使用した列に対するハッシュを返します。

rh = RollingHash.new("missisippi")
rh.hash               # => 339225237399054811
rh.hash("missisippi") # => 339225237399054811

文字列検索を行います。

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

検索を行います。

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

文字列検索を行います。

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

検索を行います。

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

s[i...] と other[j...] の最長共通接頭辞の長さを返します。

other はデフォルトで自分自身を渡しています。 自分自身以外を渡す場合は $(mod, base)$ が一致している必要があります。

rh1 = RollingHash.new("missisippi")
rh1 = rh1.lcp(3, 5) # => 2
rh1 = rh1.lcp(0, 1) # => 0

range で指定した範囲 s[range] のハッシュを返します。

rh = RollingHash.new("missisippi")
rh.slice(4..5) # => 339225237399054811
rh.slice(5..6) # => 339225237399054811

s[start...start + length] のハッシュを返します。

rh = RollingHash.new("missisippi")
rh.substr(4, length: 2) # => 339225237399054811
rh.substr(5, length: 2) # => 339225237399054811