文字列アルゴリズム

1. Rolling Hash

(1) 概要

長さ$ Nの2つの文字列が等しいかどうか判定する．

判定には通常$ O(N)必要なところ，文字列をハッシュ化しておくことで$ O(1)で判定する．

前処理として，文字列のハッシュ値を作成する処理を効率化する．

(2) 処理の流れ

hash[i]：文字列の先頭からi文字までの部分文字列に対するハッシュ値を求める．累積和と同じ考えを使って，hash[1]～hash[N]までを$ O(N)で作成可能

文字列のi文字目からj文字目までの部分文字列に対するハッシュ値は，累積和と同じ考え方を使って，hash[i]とhash[j]を使って$ O(1)で求めることができる．

上の処理を行うためには，基数の累乗の計算が必要．これも$ O(N)で前処理で求めておく．

(3) 参考サイト

Rolling Hashのおはなし

(4) 練習問題

競技プログラミングの鉄則，A56 String Hash　https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bd

2. Zアルゴリズム

(1) 概要

文字列Sに対する最長共通接頭辞の長さのリスト（Z配列）を求める

単純な方法だと$ O(|S|^2)のところ，$ O(|S|)で求める

(2)最長共通接頭辞の長さ（Z配列）とは

0-indexedで考える

Z[i]は，文字列Sと，i文字目から始まるS[i:]とを比較して，先頭から共通する文字の長さ

https://scrapbox.io/files/63c0bee52acf37001d24aba1.png

上の例だと，SとS[2:]とが，"あいあ"まで共通するので，Z[2]=3となる

Z[0]はSとSとの比較になるため，必ずZ[0]=len(S)になる

(3) 効率化

https://scrapbox.io/files/63c0c0c874d30b001d1d8e59.png

Z[10]まで求めた状態を考える．

Z[10]=5ということは，10文字目からの5文字（14文字目まで）は，0文字目からの5文字（4文字目まで）と同じ，ということ

じゃあ，Z[11], Z[12], Z[13], Z[14]って，Z[1], Z[2], Z[3], Z[4]と同じになるんじゃね？

https://scrapbox.io/files/63c0c262bee01c001e0a4637.png

例えばZ[12]を確認すると，確かにZ[2]と同じになる．

https://scrapbox.io/files/63c0c30d967e10001d7718aa.png

このSでは，Z[11], Z[12], Z[13], Z[14] = Z[1], Z[2], Z[3], Z[4]となる．i=11, ..., 14は最長共通接頭辞の長さチェックをする必要がなく，i=15から最長共通接頭辞の長さチェックを行えばよい．

(4) 反例

上のロジックが適用できない場合もある．

https://scrapbox.io/files/63c0c4d770277c001eccf4ed.png

先の例でS[15]="い"に変更した例．

Z[10]=5までは先の例と同じ．しかし，Z[12]=4となり，Z[2]とは異なる．

原因は，Z[10]=5で「先頭と同じ」としていた範囲の右端である「14文字目」を超えて一致したため

結論：右端に達しないなら，計算済結果を利用できる

(5) コード（参考サイト[1]のコードをPythonに変更，実行例を追加）

code:python

def z_algorithm(s: str) -> list:

n = len(s)

z = 0 * n

z0 = n

i, j = 1, 0

while i < n:

while i + j < n and sj == si + j: # 共通接頭辞の長さチェック

j += 1

zi = j

if j == 0: # j <= 1 でも良さそう．その場合は，j = 0も必要

i += 1

continue

k = 1

while i + k < n and k + ansk < j: # （文字の最後でなく，）「先頭と同じ」範囲の右端に達していないなら

zi + k = zk

k += 1

i += k

j -= k

return z

s = 'あいあいあかきかきかきこあいあいあさしさしそ'

print(z_algorithm(s)) ' 20, 0, 3, 0, 1, 0, 0, 0, 0, 0, 5, 0, 3, 0, 1, 0, 0, 0, 0, 0

s = 'あいあいあかきかきかきこあいあいあいしさしそ'

print(z_algorithm(s)) ' 20, 0, 3, 0, 1, 0, 0, 0, 0, 0, 5, 0, 4, 0, 2, 0, 0, 0, 0, 0

i ... Z[i]のインデックス．（Z[0]は自明なので）i=1から順に大きくなる

j ... Z[i]の値．順にスキャンして求める

k ... 計算済結果を利用するインデックス．Z[k]を利用する．

「先頭と同じ」としていた範囲の左端がS[i]，右端がS[i + j - 1]，範囲の大きさがjになる

(6) 参考サイト

[1] 【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く

3. Aho-Corasick法

(1) 概要

文字列$ Tの中に，複数の文字列$ S_1, S_2, ..., S_Nが含まれる（部分文字列として持つ）かどうかを判定する．

各文字列$ S_1, S_2, ..., S_Nのprefixからなるノード（トライ木）を構築して，各ノードが表す文字列が$ S_1, S_2, ..., S_Nのどれを含むかの情報を保持する．

(2) コード（参考サイトを参考に変更）

code:python

from collections import deque

class AhoCorasick:

def __init__(self, sigma=26): # 木のノードを作成する

self.node = [-1 * sigma] # nodevc: 木のノードvの状態で文字c（'a'が0，'z'が25）を受け取ったときの遷移先ノード

self.last = 0 # lastv: 木ノードvの状態で含むことができる文字の集合．bit表現

self.sigma = sigma # 候補となる文字数．小文字26文字で考える

def add(self, S): # 文字列リストSの要素sのprefixをパスを木に追加する

for ID, s in enumerate(S):

v = 0 # ルートから開始

for c in s:

idx = ord(c) - ord('a') # 小文字で何番目の文字か

if self.nodevidx == -1: # ノードvの状態から，文字cが来たときに推移するノードが未定のとき

self.nodevidx = len(self.node) # ノードvに文字cを追加した文字列を表す新しいノードを作成

self.node.append(-1 * self.sigma) # そのノードからの遷移先はすべて未定

self.last.append(0) # そのノードに到着しても，含む文字は（とりあえず）何もない

v = self.nodevidx # 現在のノードを，ノードvに文字cを追加したノードに移動

self.lastv |= 1 << ID # ノードvが文字列s自体を表すなら，ノードvは文字列sを含むことを登録

def build(self, S): # AC木の情報を構築する（各文字列がaddされたあとに実行）

self.add(S) # 文字列Sに含まれる各文字sのprefixをパスとする木を作る

link = 0 * len(self.node) # linkv: ノードvが表す文字列sに続く文字がないとき，sの先頭を除いたs1:（またはs1:と同じ状態）のノード

que = deque() # BFS用のキュー

for i in range(self.sigma): # ルート情報の構築．ルートから各1文字c（i番目の文字）を追加した文字列を表すノードを考える

if self.node0i == -1: # 文字cだけを表すノードが存在しないなら

self.node0i = 0 # 文字cだけを表すノードは，ルートと同じ状態

else: # 文字cだけを表すノードが存在するなら

link[self.node0i] = 0 # 文字cから1文字削除したらルートに戻る

que.append(self.node0i) # BFSで次は文字cだけを表すノードから探索を始める

# BFS

while que:

v = que.popleft() # 先頭のノードを獲得．文字数の少ない順に探索される（同じ文字数なら順不同）

self.lastv |= self.last[linkv] # ノードvが含む文字列の集合に，先頭の1文字削除した文字列を表すノードが含む文字列を追加する（BFSなので，1文字少ないノードは探索済み）

for i in range(self.sigma): # 各小文字c（i番目の文字）を追加する

u = self.nodevi # ノードvが表す文字列にcを追加した文字列が表すノード

if u == -1: # そんな文字列が登録されていないなら

self.nodevi = self.node[linkv]i # 先頭の1文字を削除して文字列cを追加して推移するノードと意味が同じになる

else: # ノードvが表す文字列にcを追加した文字列が登録済み（ノードu）なら

linku = self.node[linkv]i # ノードuの先頭1文字削除した文字列＝ノードvの先頭1文字を除いた文字列＋文字列c

que.append(u) # BFSの候補にノードuを追加

# 例1： S = 'ab', 'b'

# 作成されるノード：

# 0: 文字列 '', 推移先ノード: a -> 1(a), b -> 3(b)

# 1: 文字列 'a' 推移先ノード: a -> 1(a), b -> 2(ab)

# 2: 文字列 'ab' 推移先ノード: a -> 1(a), b -> 3(b)

# 3: 文字列 'b' 推移先ノード: a -> 1(a), b -> 3(b)

# 含む文字列： 0('') -> なし，1(a) -> なし，2(ab) -> ab/b = 3，3(b) -> b = 2

AC = AhoCorasick() # Aho_Corasickクラスのインスタンス生成

S = 'ab', 'b' # 候補となる文字列集合

AC.build(S) # Aho_Corasickのフィールドを構築

print(len(AC.node)) # ノード数 4

print(*(AC.node), sep='\n') # 1, 3, 0..., 1, 2, 0..., 1, 3, 0..., 1, 3, 0...

print(AC.last) # 0, 0, 3, 2

# 例2： S = 'abc', 'bc', 'c

# 作成されるノード：

# 0: 文字列 '', 推移先ノード: a -> 1(a), b -> 4(b), c -> 6(c)

# 1: 文字列 'a' 推移先ノード: a -> 1(a), b -> 2(ab), c -> 6(c)

# 2: 文字列 'ab' 推移先ノード: a -> 1(a), b -> 4(b), c -> 3(abc)

# 3: 文字列 'abc' 推移先ノード: a -> 1(a), b -> 4(b), c -> 6(c)

# 4: 文字列 'b' 推移先ノード: a -> 1(a), b -> 4(b), c -> 5(bc)

# 5: 文字列 'bc' 推移先ノード: a -> 1(a), b -> 4(b), c -> 6(c)

# 6: 文字列 'c' 推移先ノード: a -> 1(a), b -> 4(b), c -> 6(c)

# 含む文字列： 0, 1, 2('', a, ab) -> なし，3(abc) -> abc/bc/c = 7，4(b) -> なし，5(bc) -> bc/c = 6, 6(c) -> c = 4

AC = AhoCorasick() # Aho_Corasickクラスのインスタンス生成

S = 'abc', 'bc', 'c' # 候補となる文字列集合

AC.build(S) # Aho_Corasickのフィールドを構築

print(len(AC.node)) # ノード数 7

print(*(AC.node), sep='\n') # 1, 4, 6, 0..., 1, 2, 6, 0..., 1, 4, 3, 0..., 1, 4, 6, 0..., 1, 4, 5, 0..., 1, 4, 6, 0..., 1, 4, 6, 0...

print(AC.last) # 0, 0, 0, 7, 0, 6, 4

(3) 参考サイト

ABC419F 解説 https://atcoder.jp/contests/abc419/editorial/13623

#文字列アルゴリズム #RollingHash #Zアルゴリズム