差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:string_search [2020/01/16] – [Aho-Corasick 法] ikatakos
+++ programming_algorithm:string_search [2024/07/29] (現在) – [Aho-Corasick 法] ikatakos
@@ 行 3: / 行 3: @@
 執筆途中（多分永遠に）
+  * [[wpjp>文字列探索]]
+  * [[wp>String-searching_algorithm]]
   * [[https://www.hamayanhamayan.com/entry/2017/03/25/005452|競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree] - はまやんはまやんはまやん]]
+文字列に関連したアルゴリズムをメモしていく。
+つ1つはリンクを参照し詳しくは解説しないが、イメージ的なものと実装例は（なるべく）自分用に書いておく。
+長くなりすぎたら分けるかも。
+文字列と言いつつプログラム上は文字コードの数列なので、元から数列であるデータを処理する際にもアルゴリズムは適用できる。
+文字列に関するアルゴリズムは、主に「検索」や「汎用的なデータ構造を構築」するものが多い。
+===== 文字列アルゴリズム全体に関連することとか =====
+=== 計算量 ===
+文字列アルゴリズムに限定した話ではないが、特に文字列では「平均計算量」と「最悪計算量」に差があるものが多く、この概念を区別したい。
+文字列比較を例に取ると、通常の言語ではだいたいすぐ失敗するのに対し、
+わざと一致箇所が多くなるような意地悪な入力を与えると非常に多くの比較を行わなければならない、というケースがある。
+  * 'apple' と 'orange' は一致しますか？
+    * →1文字目で失敗するのですぐ No とわかる
+  * 'aaaaa.....aa' と 'aaaaa...ab' は一致しますか？（10万文字）
+    * →先頭から10万回比較しないとわからない
+競技プログラミングではだいたいこういう意地悪ケースが入っているので最悪計算量を意識する必要があるが、実用の上では平均計算量も（というかそちらの方が）重要。
+ただ、明確に区別しづらかったり、正確な計算量の特定が難しかったりで、各アルゴリズムについて平均と最悪を必ずしも書いてはいない。
+=== 記号 ===
+以下、アルゴリズムの対象文字列を  $S$  とする。
+検索の場合は、被検索対象を  $S$  とし、見つけ出す文字列を  $T$  とする。
+それぞれが複数ある場合もあるため、それらをまとめて示す場合は  $\mathbb{S},\mathbb{T}$  とし、個々の1要素を  $S,T$  とする。
+ $S$  の  $i$  文字目を  $S_i$  と表す。
+ $S$  の長さを  $|S|$  で表す。
 ===== 文字列検索アルゴリズム =====
@@ 行 10: / 行 52: @@
 ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するより''find()''など組み込み関数を使った方が一般的には高速となる。
+（むしろ以下の内容が既に実装されているはず）
  $S$  や  $T$  が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。
 ==== 愚直（Brute Force） ====
+==計算量==
+ $O(|S||T|)$
+==概要==
 まずは基本。マッチ位置  $i$  を1つずつずらして、そこから各  $j$  文字目が一致するか照合していく。
-  S  ABCDEABCF
+     S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...    ABCDEABCF
-  T  ABCF
+     T  ABCF          ABCF          ABCF       ...         ABCF
-      ABCF
+  照合  ooox          x             x          ...         oooo  発見!
-       ABCF
-一般的な（言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ  $O(|S|)$  で済むが、
+一般的な（自然言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ  $O(|S|)$  で済む。
-同じ文字が多く出現する特殊な場合は、最悪  $O(|S||T|)$  かかる。
 ++++ Pythonでの実装例 |
@@ 行 46: / 行 93: @@
   * [[wpjp>クヌース–モリス–プラット法]]
   * [[https://youtu.be/9MphwmIsO7Q?t=7313|AtCoder Beginner Contest 150 解説]]
+==計算量==
+前計算  $O(|T|)$ 、検索  $O(|S|)$
+==概要==
 対1の検索アルゴリズム。
- $T$  から「 $j$  文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。
+事前に  $T$  から「 $j$  文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。
+++++ もう少し詳細 |
+  前計算テーブル
   j  012345             0  1  2  3  4  5
   T  ABCABD  →  Tbl: [-1, 0, 0, 0, 1, 2]
-たとえば  $j=5$  文字目の'''D'''で失敗したら、次のマッチ位置では既に'AB'が一致していることが分かるので、2文字飛ばせることを示す。
+たとえば  $j=5$  文字目の'''D'''で失敗したら、次は0,1文字目の'AB'を3,4文字目に合わせた位置で照合を行えばよい（それより左ではもはや一致しないことが  $T$  だけからわかる）。
+さらにそのマッチ位置では既に'AB'が一致しているので、2文字飛ばせる。
   S  ABCABCABD
@@ 行 61: / 行 118: @@
   S  ABCABCABD
-  T     ABCABD    ここまでずらせる （i ← i+j-Tbl[j], j ← Tbl[j]）
+  T     ABCABD    ここまでずらせる
           ^^^^    さらに'AB'を飛ばして'C'から探索開始すればいい
+具体的には、 $S$  の  $i+j$  文字目と  $T$  の  $j$  文字目を照合しつつ  $j$  文字目で失敗した場合、次の位置は以下のようにすればよい。
+  *  $i ← i+j-Tbl[j]$
+  *  $j ← Tbl[j]$
 ''Tbl[0] = -1'' となっているのは便宜的なもので、 $j=0$  文字目で失敗した際に次のマッチ位置を1つ進めるため。
-（基本的に照合失敗したら  $T$  をずらして、失敗した  $S$  側の文字はもう一度  $T$  と照合されるが、 $j=0$  の場合のみ、 $S$  側の文字も進める必要がある）
-計算量は、テーブル作成 $O(|T|)$、探索 $O(|S|)$ で行える。
+照合失敗したら、基本的には失敗した  $S$  側の文字はもう一度  $T$  と照合されるが、 $j=0$  の場合のみ、 $S$  側の文字も進める必要がある。
+++++
 ++++ Pythonでの実装例 |
@@ 行 118: / 行 181: @@
   * [[wpjp>ボイヤー-ムーア文字列検索アルゴリズム]]
+==概要==
 対1の検索アルゴリズム。
-KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。
+KMP法同様、テーブルを作ってマッチ位置をスキップするのだが、文字の照合は後ろからおこなうのが特徴。
-これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。
+==計算量==
+前計算  $O(|T|)$ 、検索はランダムケースならほぼ  $O(\frac{|S|}{|T|})$ 、最悪  $O(|S||T|)$ （最悪を  $O(|S|)$  にする改善方法は存在）
+++++ もう少し詳細 |
+後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。
+そのため実用上よく使われている。
 だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。
@@ 行 134: / 行 207: @@
           x^           末尾から2番目で照合失敗、失敗時のS側の文字は'C'
   S  ...AB[C]DEFGH...
-  T     CA[C]ABD       失敗位置より左にはじめて出現する'C'までは飛ばせる（[]を合わせる感じ）
+  T     CA[C]ABD       失敗位置より左にはじめて出現する'C'までは飛ばせる（[ ]を合わせる感じ）
                x       再度末尾から検索するが、1番目で一致しない
   S  ...ABCDEFGH...
   T           CACABD   'F'はTに出現しないので、丸ごと飛ばせる
-一般的な意味のある文字列では、ほぼ  $|T|$  ずつ枠が移動し、  $O(\frac{|S|}{|T|})$  となる。
+一般的な文字列では、ほぼ  $|T|$  ずつ枠が移動し、  $O(\frac{|S|}{|T|})$  となる。
 一方、 $S$  や  $T$  に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪  $O(|S||T|)$  となる。
@@ 行 161: / 行 234: @@
                         また、この照合では先頭の'BC'は一致がわかっているので比較しなくてよい
 */
+++++
 ==== Rabin-Karp法（ローリングハッシュ） ====
@@ 行 166: / 行 241: @@
   * [[wpjp>ラビン-カープ文字列検索アルゴリズム]]
-一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。
+== 概要 ==
-=== 計算量 ===
+一定の長さの文字列をハッシュ化（1つの整数）にした上で、ハッシュ値で検索するアルゴリズム。
+対1でも使えるし、 $T$  が複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。
+== 計算量 ==
 ハッシュ化に  $O(|S|+|T|)$ 、検索に  $O(|S|)$
-=== 概要 ===
+++++ もう少し詳細 |
-KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。
+KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。
-事前計算として、 $S$  から開始位置を1つずつずらしたハッシュ列  $S'$  を作成しておく。
+事前計算として、 $S$  から長さ  $|T|$  の文字列を切り出したハッシュ列  $S'$  を開始位置を1つずつずらして作成しておく。
  $T$  も全体のハッシュ値  $T'$  を求める。
 すると検索は、数列  $S'$  から1つの数字  $T'$  を探す処理になる。
+  S = a b c a b c d
+                        ハッシュ値
+      a b c a        →   53
+        b c a b      →   27
+          c a b c    →   38
+            a b c d  →    5
+  S' = [ 53, 27, 38, 5 ]
+  T = a b c d        →  T' = 5
  $T$  が複数ある場合、長さが同じであれば、 $S'$  を共有できる。
 ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。
-整数  $X$  と  $M$  を決め、文字列を  $X$  進法の数字とみなす。大きくなりすぎるので  $M$  でmodを取る。
+アイデアとしては、整数  $X$  と  $M$  を決め、文字列を  $X$  進法の数字とみなす感じ。大きくなりすぎるので  $M$  でmodを取る。
 比較的理解と実装が簡単だが、ハッシュ衝突（違う文字列が同じハッシュ値になってしまう）があるので、なるべく  $M$  を大きい素数とし、 $X$  を変えて2～3回試すのがよい。
@@ 行 191: / 行 281: @@
   * [[https://qiita.com/keymoon/items/11fac5627672a6d6a9f6|安全で爆速なRollingHashの話 - Qiita]]
-またこれは、2次元にも拡張できる。
+またこれは、2次元にも拡張できる。（ある矩形領域が特定のパターンである場所はあるか？その位置は？）
+++++
 ++++ Pythonでの実装例 |
@@ 行 268: / 行 360: @@
   * [[https://naoya-2.hatenadiary.org/entry/20090405/aho_corasick|Aho Corasick 法 - naoyaのはてなダイアリー]]
-主に  $T$  が複数ある場合に用いる。
+==概要==
- $T$  の集合をTrie木化しておくことで、 $S$  にどれが含まれているかを $O(|S|)$ で一括に検索できる。
+主に  $T$  が複数ある場合に用いる（ $T$  の集合を $\mathbb{T}=(T_1,T_2,...)$ で表す）。
-実装としてはTrie木に辺を追加して、「検索に失敗したとき、次に一致する可能性のある  $T$  を探すにはどのノードから再開すればいいか」を効率化している。
+ $\mathbb{T}$  の方を前計算するので、$\mathbb{T}$ は固定的であり、 $S$  の方を様々に変更して検索する用途に向く。
-構築の方法と何故それで上手くいくのかについては、naoya氏のブログを参照。
+前計算の実装としては、 $\mathbb{T}$  からTrie木を構築、
+さらに「検索に失敗したとき、次に一致する可能性のある  $T$  を探すにはどのノードから再開すればいいか」を前計算し、
+オートマトンを生成する。
+検索では  $S$  を1文字ずつ順番に見て、前計算結果に従い遷移する。
+==計算量==
+ $\mathbb{T}$  の各要素の長さの合計  $\sum{|T_i|}=m$  とすると、
+前計算の構築に  $O(m)$ 、検索に  $O(|S|+m+マッチ数)$
+++++ もう少し詳細 |
+==failureの構築==
+Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(failure)を特定する。
+  * '''abcd''' のfailureは、
+    * '''abc''' のfailureの子に '''d''' が
+      * ある→その子
+      * ない→'''abc'''のfailureのfailureの子に '''d''' が
+        * ある→その子
+        * ない→...
+        * failureを再帰的に遡り、根まで遡っても無ければ、根
+幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。
+== 含まれているのに訪れられないノードへの対処 ==
+ $S=$  '''abcde''' の中から  $\mathbb{T}=$ ''{'cd', 'bcde', 'abcdz'}'' を探すことを考える。\\
+ $S$  をルートから辿る過程で、 $T_i$  を示す終端ノードに訪れたら、
+ $S$  中に  $T_i$  が出現していることがわかる。
+  ○ -- a -- ab -- abc -- abcd -- abcdz
+   |      ↙    ↙     ↙
+   |--- b -- bc -- bcd -- bcde       ↙: failureリンク。
+   |      ↙    ↙                       特に示されないノードのfailureは根へのリンク
+   `--- c -- cd
+''a→ab→abc→abcd'' のノードまで辿った後、次の'''e'''が無いのでfailureを辿って'''bcd'''のノードに移り、
+その後'''bcde'''が見つかって終わりになる。
+実際は'''cd'''も含まれるのに、'''cd'''のノードは一回も訪れられない。\\
+これは、'''cd'''が'''abcdz'''や'''bcde'''に内包されてしまっており、
+ $S$  が探索中に訪れるのは「最も長く一致しているノード」であるためである。\\
+（ $S$  を'abcd' まで探索時、訪れるノードとして可能性があるのは（検索対象として存在しないものも含め）'abcd'の suffix である abcd,bcd,cd,d である。このうち存在する中で最も長い abcd に訪れられる）
+'''cd'''を捕捉するには、探索中の各ノードで
+「自身のfailure, failureのfailure, failureのfailureのfailure, ...」を根まで遡って調べると見つけることが出来る。\\
+上例では、'''abcd'''に訪れたとき、そのfailureのfailureが'''cd'''のため、そこで見つけることができる。
+しかし、実際にそんなことをやっていると時間がかかるので、failureを構築する過程で前計算しておく。
+各ノードが「自身からfailureを遡っていったときに見つかる文字列リスト」matchを持つ。
+  * Trie木の構築時点では、各  $T_i$  の終端を表すノードのmatchに、 $i$  を登録しておく
+  * failure構築時、自身のmatchに、自身のfailureのmatchを全て加える
+    * 根から近い方から構築するので、failureのmatchには、既にfailureのfailure以前のmatchが含まれている
+こうしておくと、'''abcd'''のノードのmatchに'cd'が登録されており、見つけることが出来る。
+  各ノードのmatchに(0:cd, 1:bcde, 2:abcdz)が含まれている場合、cd(0)のように示す
+  ■Trie木構築時点
+  ○ -- a -- ab -- abc -- abcd -- abcdz(2)
+   |
+   |--- b -- bc -- bcd -- bcde(1)
+   |
+   `--- c -- cd(0)
+  ■failure構築後
+  ○ -- a -- ab -- abc -- abcd(0) -- abcdz(2)
+   |      ↙    ↙     ↙
+   |--- b -- bc -- bcd(0) -- bcde(1)
+   |      ↙    ↙
+   `--- c -- cd(0)
+matchが肥大化し、統合に時間がかかってしまわないか？と少し思うが、
+よく考えると、1つの文字列  $T_i$  がmatchに登録されるノードの個数の上限は  $|T_i|$  なので、
+failureから子へと複製されるmatchの要素数は、 $O(\sum{|T_i|})$  で抑えられる。
+== 文字列の出現個数 ==
+上記のように、通常、Aho-Corasick では match を各ノードで事前計算し、
+ $S$  を辿る過程でmatchを参照していく。
+マッチ数が非常に多くなる場合は、探索に最悪  $O(|S| \times (1つのノードが持ちうるmatchの最大個数)$  かかってしまう。\\
+matchの最大長は  $\mathbb{T}=$ ''(a,aa,aaa,...)'' などのような場合に  $\sqrt{\sum{|T_i|}}$  であり、
+結局、 $O(|S|\sqrt{\sum{|T_i|}})$  となる。
+「各文字列の出現個数」だけが必要で出現位置は不要な場合は、持たせる情報を変えることでこの計算量を削減できる。
+  * 前計算
+    * matchは持たず、Trieとfailureリンクのみ構築する
+  * 探索
+    * 各ノードに変数 count を用意し、 $S$  からの探索で訪れるたびに +1 する
+  * 探索後
+    * 上述の「含まれているのに訪れられないノード問題」のため、根から遠いノードから「failure先のcount += 自身のcount」していく
+    * 各  $T_i$  の終端ノードの count が、出現個数となる
+これにより、計算量は  $O(|S| + \sum{|T_i|})$  となる。
+++++
 ++++ Pythonでの実装例 |
@@ 行 284: / 行 480: @@
 class AhoCorasick:
-    def __init__(self, needles):
+    def __init__(self, patterns):
+        self.patterns = patterns
         self.children = [{}]
         self.match = [[]]
-        for needle in needles:
+        for pi, pattern in enumerate(patterns):
-            self._register(needle)
+            self._register(pi, pattern)
-        self.failure = self._create_failure()
+        self.failure = [0] * len(self.children)
+        self._create_failure()
-    def _register(self, needle):
+    def _register(self, pi, pattern):
         k = 0
-        for c in needle:
+        for c in pattern:
             if c in self.children[k]:
                 k = self.children[k][c]
@@ 行 304: / 行 502: @@
                 self.match.append([])
                 k = j
-        self.match[k].append(needle)
+        self.match[k].append(pi)
     def _create_failure(self):
         children = self.children
         match = self.match
-        failure = [0] * len(children)
+        failure = self.failure
-        q = deque()
-        for k in children[0].values():
-            failure[k] = 0
-            q.append(k)
+        q = deque(children[0].values())
         while q:
             k = q.popleft()
+            b = failure[k]
             for c, j in children[k].items():
-                b = failure[k]
+                failure[j] = self._next(b, c)
-                failure[j] = self._get_next(b, c, failure)
                 match[j].extend(match[failure[j]])
                 q.append(j)
-        return failure
+    def _next(self, k, c):
-    def _get_next(self, k, c, failure):
         while True:
             if c in self.children[k]:
@@ 行 332: / 行 524: @@
             if k == 0:
                 return 0
-            k = failure[k]
+            k = self.failure[k]
-    def search(self, haystack):
+    def search(self, target):
         match = self.match
+        patterns = self.patterns
         k = 0
         matched = []
-        for i, c in enumerate(haystack):
+        for i, c in enumerate(target):
-            k = self._get_next(k, c, self.failure)
+            k = self._next(k, c)
-            for m in match[k]:
+            matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
-                matched.append((i - len(m) + 1, i, m))
         return matched
-ahc = AhoCorasick(['ab', 'bc', 'bab', 'd', 'ababcde', 'bababcde'])
+ahc = AhoCorasick(['bc', 'd', 'ababcde', 'bababcde', 'ab'])
 print(ahc.search('xbababcdex'))
-# => [(1, 3, 'bab'), (2, 3, 'ab'), (3, 5, 'bab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]
+# => [(2, 3, 'ab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]
 </sxh>
 ++++
+==== Suffix Array(SA-IS法) ====
+  * [[wpjp>接尾辞配列]]
+  * [[https://speakerdeck.com/flare/sa-is|SA-IS - Speaker Deck]]
+==概要==
+Suffix Arrayの説明自体は上のサイトや他に溢れてるので、割愛。
+これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。
+SAで文字列検索を行うには、二分探索を用いる。
+辞書順に並んでいるため、 $S$  の中に  $T$ （を接頭辞とした文字列）が出現するかどうかは二分探索で調べられる。
+複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。
+  * SA-IS法について、Rubyでの実装例を追いながら、データの中身を含めて解説してくれているサイト
+    * [[https://mametter.hatenablog.com/entry/20180130/p1|SA-IS 法のメモ - まめめも]]
+==計算量==
+  * 前計算
+    *  $O(|S|)$
+  * 検索
+    *  $O(|T| \log|S|)$
+++++ PythonでのSA-ISの実装 |
+  * ''make_suffix_array()'' を呼ぶ
+  * aaaは数列で与える点に注意（途中でsa_is()を再帰的に呼ぶが、その際にaaaは数列の方が都合がいいため）
+  * ''make_suffix_array()'' 内で末尾に最小のダミー要素として[-1]を加えているが、aaaの最小値に応じて適宜変更する
+<sxh python>
+from collections import Counter
+from itertools import accumulate
+from operator import itemgetter
+def induced_sort(n, aaa, lsa, lmss, a_acc, a_dic, ak):
+    """
+    :param lsa: L-S Array
+    :param lmss: Leftmost S の配列（この順番により結果は変化する）
+    :return:
+    """
+    sa = [-1] * n
+    counter = [0] * ak
+    for i in reversed(lmss):
+        di = a_dic[aaa[i]]
+        sa[a_acc[di + 1] - 1 - counter[di]] = i
+        counter[di] += 1
+    counter = [0] * ak
+    for i in sa:
+        if i <= 0:
+            continue
+        if lsa[i - 1] == 0:
+            continue
+        di = a_dic[aaa[i - 1]]
+        sa[a_acc[di] + counter[di]] = i - 1
+        counter[di] += 1
+    counter = [0] * ak
+    for i in reversed(sa):
+        if i <= 0:
+            continue
+        if lsa[i - 1] == 1:
+            continue
+        di = a_dic[aaa[i - 1]]
+        sa[a_acc[di + 1] - 1 - counter[di]] = i - 1
+        counter[di] += 1
+    return sa
+def sa_is(n: int, aaa: list, a_acc: list, a_dic: dict, ak: int):
+    """
+    :param n: aaaの長さ
+    :param aaa: Suffix Arrayを求めたい数列
+               （初回呼び出し時は末尾に最小ダミー要素を1つ追加すること）
+    :param a_acc: 頭文字がa_dic[a]の要素がSA上で並び始めるindex
+    :param a_dic: aaaの各要素に昇順に割り当てる連番
+    :param ak: aaaに出現する要素の種類数（len(a_dic)）
+    :return:
+    """
+    # LS array
+    lsa = [0] * n  # 0:S, 1:L
+    for i in range(n - 2, -1, -1):
+        if aaa[i] == aaa[i + 1]:
+            lsa[i] = lsa[i + 1]
+        elif aaa[i] > aaa[i + 1]:
+            lsa[i] = 1
+    # LeftMost S
+    lmss = [i for i, (lsl, lsr) in enumerate(zip(lsa, lsa[1:]), start=1)
+            if lsl == 1 and lsr == 0]
+    sa = induced_sort(n, aaa, lsa, lmss, a_acc, a_dic, ak)
+    lms_set = set(lmss)
+    sa = [i for i in sa if i in lms_set]
+    nums = [-1] * n
+    nums[sa[0]] = num = 0
+    for i, j in zip(sa, sa[1:]):
+        for d in range(n):
+            is_id_lms = i + d in lms_set
+            is_jd_lms = j + d in lms_set
+            if aaa[i + d] != aaa[j + d] or (is_id_lms != is_jd_lms):
+                num += 1
+                break
+            elif d > 0 and (is_id_lms or is_jd_lms):
+                break
+        nums[j] = num
+    nums = [i for i in nums if i != -1]
+    if num < len(nums) - 1:
+        sa = sa_is(num + 1, nums)
+        lmss2 = list(map(lmss.__getitem__, sa))
+    else:
+        lmss2 = [lmss[i] for i, j in sorted(enumerate(nums), key=itemgetter(1))]
+    sa = induced_sort(n, aaa, lsa, lmss2, a_acc, a_dic, ak)
+    return sa
+def make_suffix_array(aaa):
+    n = len(aaa)
+    a_cnt = Counter(aaa)
+    a_kind = sorted(a_cnt.keys())
+    a_dic = {a: i for i, a in enumerate(a_kind)}
+    a_acc = list(accumulate([0] + list(map(a_cnt.get, a_kind))))
+    ak = len(a_kind)
+    # [-1] はaaa内のどの要素より小さい要素（適宜変更する）
+    sa = sa_is(n + 1, aaa + [-1], a_acc, a_dic, ak)
+    return sa
+</sxh>
+++++
+==== FM-index ====
+  * [[wp>FM-index]]
+  * [[https://www.slideshare.net/kujira16/fmindex|FM-indexによる全文検索]]
+==概要==
+主に  $T$  が複数ある場合に用いる。（別に複数で無くてもよいが、1対1なら前処理にかかる時間を考えると他のアルゴリズムを用いた方がよい）
+ $S$  を前計算するので、 $S$  が固定的であり、 $T$  を様々に変えて検索する用途に向く。
+前計算では  $S$  をBWT(Burrows Wheeler変換)しておき、検索で  $T$  の各接尾辞が出現するかをチェックする。
+これまでのアルゴリズムと比べて新しく、性能はいいが理解・実装も複雑。
+==計算量==
+  * 前計算
+    * 理解しやすいが低速  $O(|S|^2 \log{|S|})$
+    * 難しいが高速  $O(|S| \log{|S|})$
+    *  $O(|S|)$  などのアルゴリズムもあるが、自然言語に対しては実用上、上の方がよいらしい
+  * 1回の検索
+    * 出現する文字の種類数を  $\sigma$  として、 $O(|T| \log{\sigma})$
+==== FFT（畳み込み） ====
+  * [[programming_algorithm:fft]]
+  * [[https://manabitimes.jp/math/954|合成積（畳み込み）の意味と応用３つ | 高校数学の美しい物語]]
+== 概要 ==
+畳み込みは別に文字列に限定したアルゴリズムでは無いのだが、少し応用の利いた一致箇所の列挙に使える。
+ $T$  を反転させたものを  $U$  とし、 $S,U$  の各文字を対応する何らかの数値に置き換える。
+すると、 $S,U$  の畳み込み結果の数列は、
+「 $S_i$  と  $T_1$  の位置を合わせた時の  $S_iT_1+S_{i+1}T_2+...+S_{i+|T|-1}T_{|T|}$ 」をそれぞれ表す。
+結果の値から、両者が一致しているかどうかを特定できるような数値への置き換えをしておけば、一致箇所を列挙できる。
+== 計算量 ==
+  *  $N=|S|+|T|$  として、 $O(N \log{N})$
+++++ もう少し詳細 |
+単純な検索なら、他の方法では  $O(|S|+|T|)$  とかでできるので、わざわざlogが付いてしまうこの方法を使う意味はあまりない。
+しかし、少し応用の利いた検索をしたいとき、他ではできないことができる。
+  * 例)
+  * 文字種が2のみのとき、各位置で合わせたときに一致する/異なる文字数を数える
+  * ワイルドカードを許容して一致判定する
+畳み込み結果（ $H$  とする）では、2つの数列の「係数の和が一致するもの同士のかけ算」の総和が求まる。
+  i        6 7 8
+  S:  ... ＡＢＣ ...
+            ＊           H[8] = A*A + B*B + C*C
+  U:      ＣＢＡ
+  j        0 1 2
+ $U$  を反転前の  $T$  に戻すと、合わせた位置が一致するもの同士のかけ算の総和が求まっていることになる。
+  i        6 7 8
+  S  ...  ＡＢＣ ...
+          ｜｜｜         H[8] = A*A + B*B + C*C
+  T       ＡＢＣ                ~~~~~~~~~~~~~~~
+  j        2 1 0         一致位置 iをずらしつつの、それぞれのこの値が一気に求まる
+畳み込み結果の長さは  $|S|+|T|-1$  となるが、前後のそれぞれ  $|T|-1$  項は、除いて考える。
+  i     0 1 ...
+  S:   ＡＢ ...  たとえば H[1] はこんな位置で合わせた結果を示すが、
+  U: ＣＢＡ      はみ出ているので意味を成さない
+  j   0 1 2
+畳み込み結果の値から、一致判定（または求めたい値）をちゃんと得られるような、 $S,U$  の数値への置き換えが肝となる。
+== ワイルドカードで一致判定 ==
+ $T$  の中に、"?"（ワイルドカード、この文字は何の文字であってもよい）が含まれるとする。
+  S: ABCDAEFD
+  T: A??D      → ABCD と AEFD で一致
+確率的なアルゴリズムになるが、文字種分だけの素数を用意して、
+  S: a→2,   b→3,   c→5,   ...
+  U: a→1/2, b→1/3, c→1/5, ..., ?→0
+などと、同じ文字を  $S$  と  $U$  で逆数の関係にある数に置き換える。ワイルドカードは0とする。
+すると、畳み込みの結果は、\\
+一致する箇所では「 $T$  に含まれるワイルドカードでない文字数」の値になり、\\
+一致しない箇所では他の異なる値になる（可能性が高い）。
+一致する箇所が一致しないと誤判定されることはないが、一致しない箇所が一致すると誤判定されることは生じる。\\
+素数の割り当てを何回か変えて試すとよい。
+または、以下で紹介されているアルゴリズムは少し複雑だが、より正答する確率評価がちゃんとできている方法となる。
+  * [[https://atcoder.jp/contests/abc307/editorial/6598|解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）]]
+++++
 ===== 文字列を効率的に保持するアルゴリズム =====
@@ 行 358: / 行 803: @@
   * [[wpjp>基数木]]
-検索手法というか、データ構造。複数の文字列を木構造で表現する。
+複数の文字列を木構造で表現するデータ構造。
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。
+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
@@ 行 378: / 行 823: @@
   * [[https://naoya-2.hatenadiary.org/entry/20081016/1224173077|Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー]]
-検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。
+文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。
 主に圧縮の前処理に用いる（同じ文字が連続していれば圧縮効率がよくなる）
@@ 行 389: / 行 834: @@
 ==== Manacher ====
-文字列  $S$  から奇数長の最長の回文を  $O(|S|)$  で検索するアルゴリズム。
   * [[https://snuke.hatenablog.com/entry/2014/12/02/235837|文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ]]
- $S$  の各文字の間に  $S$  には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる（ダミー文字が中心になったとき）。
+==概要==
+文字列  $S$  が与えられたとき、各文字につき「その文字を中心とする奇数長の回文の最大半径」を  $O(|S|)$  で求めるアルゴリズム。
+  abcdcbc  文字 d を中心とした回文の半径は 3。（中心の d から、c,b までの計3文字）
+   ~~~~~   結果として [ 1 1 1 3 1 2 1 ] という配列が得られる
+ $S$  の各文字の間に  $S$  には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる。
+++++ Pythonでの実装 |
+両端と各文字の間に'$'を挿入すると、「各要素の値-1」がそこを中心とした回文の長さとなる。
+<sxh python>
+def manacher(s):
+    n = len(s)
+    radius = [0] * n
+    i, j = 0, 0
+    while i < n:
+        while i - j >= 0 and i + j < n and s[i - j] == s[i + j]:
+            j += 1
+        radius[i] = j
+        k = 1
+        while i - k >= 0 and i + k < n and k + radius[i - k] < j:
+            radius[i + k] = radius[i - k]
+            k += 1
+        i += k
+        j -= k
+    return radius
+s = 'abcbcdcbcba'
+s = ' $' + '$ '.join(s) + '$'
+man = manacher(s)
+print(man)
+#        a     b     c     b     c      d     c     b     c     b     a
+# => [1, 2, 1, 2, 1, 4, 1, 4, 1, 2, 1, 12, 1, 2, 1, 4, 1, 4, 1, 2, 1, 2, 1]
+s = 'abccba'
+s = ' $' + '$ '.join(s) + '$'
+man = manacher(s)
+print(man)
+#        a     b     c     c     b     a
+# => [1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1]
+</sxh>
+++++