−目次

文字列アルゴリズム

文字列アルゴリズム

執筆途中（多分永遠に）

文字列に関連したアルゴリズムをメモしていく。

1つ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|$ で表す。

文字列検索アルゴリズム

文字列 $S$ から文字列 $T$ を検索する手法あれこれ。

ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するよりfind()など組み込み関数を使った方が一般的には高速となる。（むしろ以下の内容が既に実装されているはず）

$S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。

愚直（Brute Force）

計算量

$O(|S||T|)$

概要

まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。

   S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...    ABCDEABCF
   T  ABCF          ABCF          ABCF       ...         ABCF
照合  ooox          x             x          ...         oooo  発見!

一般的な（自然言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済む。

Pythonでの実装例

KMP法

計算量

前計算 $O(|T|)$ 、検索 $O(|S|)$

概要

1対1の検索アルゴリズム。

事前に $T$ から「 $j$ 文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。

もう少し詳細

前計算テーブル
j  012345             0  1  2  3  4  5
T  ABCABD  →  Tbl: [-1, 0, 0, 0, 1, 2]

たとえば $j=5$ 文字目の'D'で失敗したら、次は0,1文字目の'AB'を3,4文字目に合わせた位置で照合を行えばよい（それより左ではもはや一致しないことが $T$ だけからわかる）。さらにそのマッチ位置では既に'AB'が一致しているので、2文字飛ばせる。

S  ABCABCABD
T  ABCABD
   ^^^^^x       ここで失敗 （i=0, j=5）

S  ABCABCABD
T     ABCABD    ここまでずらせる
        ^^^^    さらに'AB'を飛ばして'C'から探索開始すればいい

具体的には、 $S$ の $i+j$ 文字目と $T$ の $j$ 文字目を照合しつつ $j$ 文字目で失敗した場合、次の位置は以下のようにすればよい。

$i ← i+j-Tbl[j]$
$j ← Tbl[j]$

Tbl[0] = -1 となっているのは便宜的なもので、 $j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。

照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、 $j=0$ の場合のみ、 $S$ 側の文字も進める必要がある。

Pythonでの実装例

Boyer-Moore 法

ボイヤー-ムーア文字列検索アルゴリズム

概要

1対1の検索アルゴリズム。

KMP法同様、テーブルを作ってマッチ位置をスキップするのだが、文字の照合は後ろからおこなうのが特徴。

計算量

前計算 $O(|T|)$ 、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$ 、最悪 $O(|S||T|)$ （最悪を $O(|S|)$ にする改善方法は存在）

もう少し詳細

後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。そのため実用上よく使われている。だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。

あらかじめ $T$ からテーブルを作成する。ただ、テーブルの作り方も複数あって、「不一致文字規則」「一致suffix規則」「両方計算してスキップできる距離の大きい方」が存在する。不一致文字規則は実装は簡単だが、文字の種類が少ない場合に効果が少ない。一致suffix規則はちょっと複雑。

不一致文字規則の例
S  ...ABCDEFGH...
T   CACABD
        x^           末尾から2番目で照合失敗、失敗時のS側の文字は'C'
S  ...AB[C]DEFGH...
T     CA[C]ABD       失敗位置より左にはじめて出現する'C'までは飛ばせる（[ ]を合わせる感じ）
             x       再度末尾から検索するが、1番目で一致しない
S  ...ABCDEFGH...
T           CACABD   'F'はTに出現しないので、丸ごと飛ばせる

一般的な文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。

一方、 $S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。

検索アルゴリズム (4) 文字列の検索 -2-

Horspoolのアルゴリズム、Sundayのアルゴリズムでは、不一致となったときに参照する文字を変えることで、実用上の平均計算時間が改善する。

線形時間を保証するには、移動量テーブル作成時、「不一致となった所までは一致していた」という情報を使う Galil 規則というものを導入すればよい。

Rabin-Karp法（ローリングハッシュ）

ラビン-カープ文字列検索アルゴリズム

概要

一定の長さの文字列をハッシュ化（1つの整数）にした上で、ハッシュ値で検索するアルゴリズム。

1対1でも使えるし、 $T$ が複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。

計算量

ハッシュ化に $O(|S|+|T|)$ 、検索に $O(|S|)$

もう少し詳細

KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。

事前計算として、 $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を取る。

比較的理解と実装が簡単だが、ハッシュ衝突（違う文字列が同じハッシュ値になってしまう）があるので、なるべく $M$ を大きい素数とし、 $X$ を変えて2～3回試すのがよい。その際、Hackのある競プロサイトでは撃墜されるのを防ぐため、ランダム化するのを推奨されている。

またこれは、2次元にも拡張できる。（ある矩形領域が特定のパターンである場所はあるか？その位置は？）

Pythonでの実装例

Bitap法

Bitapアルゴリズム

1対1の検索アルゴリズム。

照合状態をbit列であらわし、 $S$ を1文字ずつ進めながらbit演算で遷移させていく。

下から $i$ 桁目が'1'であれば、 $T$ の先頭から $i$ 番目までは一致していることを表す。

またこれはあいまい検索にも対応し、「'?'は何の文字が入ってもいい」「レーベンシュタイン距離が $N$ 以下」などの検索が可能となる。

Z-algorithm

これ自体は検索ではなく、文字列 $S$ の各開始位置 $i$ に対して、「 $S$ と $S[i:]$ が先頭何文字まで一致するか？（最長共通接頭辞数）」を構築するアルゴリズム。

i  0123456789012
S  ABCABCZABCABC
Z 13003000600300

愚直にやると最悪 $O(|S|^2)$ かかるところ、一度見たところを飛ばして $O(|S|)$ でできる。

これを文字列検索に生かすには、 $S$ と $T$ を、 $S$ の中に絶対存在しない文字（ $\$$ とする）でつなぎ、 $T\$S$ とする。 $S$ の開始位置よりZ-algorithmを適用すれば、値が $|T|$ と等しくなる箇所が、 $S$ 上で $T$ が出現する位置である。

Aho-Corasick 法

概要

主に $T$ が複数ある場合に用いる（ $T$ の集合を $\mathbb{T}=(T_1,T_2,...)$ で表す）。

$\mathbb{T}$ の方を前計算するので、 $\mathbb{T}$ は固定的であり、 $S$ の方を様々に変更して検索する用途に向く。

前計算の実装としては、 $\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での実装例

        
          
          
              
              from collections import deque
 
 
class AhoCorasick:
 
    def __init__(self, patterns):
        self.patterns = patterns
        self.children = [{}]
        self.match = [[]]
 
        for pi, pattern in enumerate(patterns):
            self._register(pi, pattern)
 
        self.failure = [0] * len(self.children)
        self._create_failure()
 
    def _register(self, pi, pattern):
        k = 0
        for c in pattern:
            if c in self.children[k]:
                k = self.children[k][c]
            else:
                j = len(self.children)
                self.children[k][c] = j
                self.children.append({})
                self.match.append([])
                k = j
        self.match[k].append(pi)
 
    def _create_failure(self):
        children = self.children
        match = self.match
        failure = self.failure
 
        q = deque(children[0].values())
        while q:
            k = q.popleft()
            b = failure[k]
            for c, j in children[k].items():
                failure[j] = self._next(b, c)
                match[j].extend(match[failure[j]])
                q.append(j)
 
    def _next(self, k, c):
        while True:
            if c in self.children[k]:
                return self.children[k][c]
            if k == 0:
                return 0
            k = self.failure[k]
 
    def search(self, target):
        match = self.match
        patterns = self.patterns
 
        k = 0
        matched = []
        for i, c in enumerate(target):
            k = self._next(k, c)
            matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
        return matched
 
 
ahc = AhoCorasick(['bc', 'd', 'ababcde', 'bababcde', 'ab'])
print(ahc.search('xbababcdex'))
# => [(2, 3, 'ab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]

            

        
      

Suffix Array(SA-IS法)

概要

Suffix Arrayの説明自体は上のサイトや他に溢れてるので、割愛。これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。

SAで文字列検索を行うには、二分探索を用いる。辞書順に並んでいるため、 $S$ の中に $T$ （を接頭辞とした文字列）が出現するかどうかは二分探索で調べられる。複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。

SA-IS法について、Rubyでの実装例を追いながら、データの中身を含めて解説してくれているサイト
- SA-IS 法のメモ - まめめも

計算量

前計算
- $O(|S|)$
検索
- $O(|T| \log|S|)$

PythonでのSA-ISの実装

make_suffix_array() を呼ぶ
aaaは数列で与える点に注意（途中でsa_is()を再帰的に呼ぶが、その際にaaaは数列の方が都合がいいため）
make_suffix_array() 内で末尾に最小のダミー要素として[-1]を加えているが、aaaの最小値に応じて適宜変更する

        
          
          
              
              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

            

        
      

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（畳み込み）

概要

畳み込みは別に文字列に限定したアルゴリズムでは無いのだが、少し応用の利いた一致箇所の列挙に使える。

$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$ に含まれるワイルドカードでない文字数」の値になり、
一致しない箇所では他の異なる値になる（可能性が高い）。

一致する箇所が一致しないと誤判定されることはないが、一致しない箇所が一致すると誤判定されることは生じる。
素数の割り当てを何回か変えて試すとよい。

または、以下で紹介されているアルゴリズムは少し複雑だが、より正答する確率評価がちゃんとできている方法となる。

解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）

文字列を効率的に保持するアルゴリズム

Trie木、Patricia木

複数の文字列を木構造で表現するデータ構造。

トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）短くて似たような単語が沢山あるとき、特に効率的に保持できる。

パトリシア木は、それを複数文字も1ノードになり得るとしたもの。実装はやや複雑になるが、長い単語がある場合でも肥大化を防ぐことができる。

Suffix tree

接尾辞木
接尾辞木 (Suffix Tree) — Stringpedia 0.1.0 ドキュメント
- 実験して遊べる

Burrows Wheeler Transform

文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。主に圧縮の前処理に用いる（同じ文字が連続していれば圧縮効率がよくなる）

自然言語でもデータでも、だいたいお決まりの文字（数字）の並びというのが発生しやすいことを利用している。例えば英語では、子音の後はだいたい母音だったり、'tr', 'sh', 'ck' などが頻出しやすい。

逆に完全にランダムなデータにはあまり効かない（と思う）。

その他

Manacher

文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

概要

文字列 $S$ が与えられたとき、各文字につき「その文字を中心とする奇数長の回文の最大半径」を $O(|S|)$ で求めるアルゴリズム。

abcdcbc  文字 d を中心とした回文の半径は 3。（中心の d から、c,b までの計3文字）
 ~~~~~   結果として [ 1 1 1 3 1 2 1 ] という配列が得られる

$S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる。

Pythonでの実装