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 ]