class NgLib::RollingHash

Overview

文字列 $S$ に対して、上手なハッシュを作ることで、比較やLCPを高速に求めます。

Defined in:

nglib/string/rolling_hash.cr

Constant Summary

MOD = (1_u64 << 61) - 1

Constructors

Class Method Summary

Instance Method Summary

Constructor Detail

def self.new(a : Array(Int), base : UInt64 | Nil = nil) #

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

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

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

[View source]
def self.new(s : String, base : UInt64 | Nil = nil) #

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

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

rh = RollingHash.new("missisippi")

[View source]
def self.new(size : Int32, a : Enumerable, base : UInt64 | Nil = nil) #

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

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

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

[View source]

Class Method Detail

def self.create_base #

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

base = RollingHash.create_base
base # => 1729

[View source]
def self.lcp(rh1 : self, rh2 : self, i : Int = 0, j : Int = 0) : Int32 #

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

[View source]

Instance Method Detail

def [](range : Range(Int | Nil, Int | Nil)) : UInt64 #

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

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

[View source]
def concat(h1 : UInt64, h2 : UInt64, h2_len : Int) : UInt64 #

ハッシュ値 $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

[View source]
def hash(s : String) #

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

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

[View source]
def hash(s : Enumerable) #

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

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

[View source]
def hash : UInt64 #

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

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

[View source]
def index(t : String, offset : Int = 0) : Int32 | Nil #

文字列検索を行います。

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

[View source]
def index(t : Enumerable, offset : Int = 0) : Int32 | Nil #

検索を行います。

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

[View source]
def index!(t : String, offset : Int = 0) : Int32 #

文字列検索を行います。

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

[View source]
def index!(t : Enumerable, offset : Int = 0) : Int32 #

検索を行います。

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

[View source]
def lcp(i : Int, j : Int, other = self) : Int32 #

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

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

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

[View source]
def size : Int32 #

[View source]
def slice(range : Range(Int | Nil, Int | Nil)) : UInt64 #

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

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

[View source]
def substr(start : Int, length : Int) : UInt64 #

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

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

[View source]