4 文字列マッチングアルゴリズム（上）：BF、KMP、SUNDAY、SHIFT-AND、Hash

一部の古典的で素晴らしい単一パターンマッチング関連アルゴリズム

コース内容#

関連定義

単一パターンマッチング問題：テキスト文字列 $s$ の中で特定のパターン文字列 $t$ が出現するかを探すこと

複数パターンマッチング問題：複数のパターン文字列 $t$ を探すこと

テキスト文字列 / 母文字列：探す文字列 $s$

パターン文字列：探される文字列 $t$

テキスト文字列の長さは $m$、パターン文字列の長さは $n$

ブルートフォースマッチング法#

すべての文字列マッチングアルゴリズムの基礎

思想#

順番にパターン文字列とテキスト文字列の各位置を整列させ、完全に一致するまで続ける
その思想はすべてのマッチングアルゴリズムを理解するための基礎：漏れなく答えを見つけること
- 他のアルゴリズムの最適化の核心は重複を避け、成功しない試行を減らすこと
時間計算量：$O (m\times n)$

考察#

最初の不一致が発生したとき、ブルートフォースマッチングはどのように処理するのか？

パターン文字列の最初の位置を母文字列の 2 番目の位置とマッチングさせる
もしマッチングが成功すれば、パターン文字列の最初の位置とテキスト文字列の 2 番目の位置が等しいことを意味する
- パターン文字列の 2 番目の位置とテキスト文字列の 2 番目の位置がマッチング成功していることが分かっているので
- パターン文字列の 2 番目の位置は必ず 1 番目の位置と等しい
パターン文字列の 2 番目の位置と 1 番目の位置が等しいかどうかは、パターン文字列を取得した時点で分かる
上の図では、パターン文字列の 1 番目の位置と母文字列の 2 番目の位置をマッチングさせる必要は全くない
- それらは確実にマッチしない
確実にマッチしない位置をスキップできるかどうか、KMP アルゴリズムには独自の考えがある

KMP#

状態機械思想、自身の構造の繰り返し展開の概念

思考過程#

続けて、A、B、C の位置に注目

【仮定】黒い影の部分で不一致が発生した場合、パターン文字列 $t$ は後方に④の大きさだけ移動し、この時テキスト文字列 $s$ の②とパターン文字列 $t$ の①がマッチング成功する場合
【重要】第③部分：その左境界が $t$ の後方移動の距離を決定する [第①部分の右境界と同じ]
【A】この縦列では、必ず②=③=①が存在し、②は不一致位置に隣接している 👉 ③も不一致位置に隣接している
【B】③は実際には $t$ の接尾辞であり、①は $t$ の接頭辞 👉 ③は $t$ のある接頭辞と等しい
【C】漏れなくマッチングを保証するために、④はできるだけ小さくするべき 👉 ③はできるだけ大きくするべき
【結論】以上のことから、③を通じてマッチングプロセスを加速でき、③は不一致位置に隣接する、$t$の最長接頭辞である

問題の変換#

不一致時に対応する③の大きさを事前に得ることは、また①の大きさでもある

パターン文字列の①と③を探し、①の後ろの緑の文字を使って②の後ろの不一致位置のオレンジの文字とマッチングする
パターン文字列の各位置を考慮する必要がある：不一致の位置はパターン文字列の各位置である可能性がある
パターン文字列は事前に知られている；テキスト文字列は知られておらず、制御できない
👉 パターン文字列の $next$ 配列

next 配列#

$next [i]$：$i$ 位置がマッチング成功したが、$i+1$ 位置が不一致した場合に使用し、次回のパターン文字列のマッチングのオフセットとして
状態定義：$i$ 位置で終わる接尾辞の中で、マッチング可能な最長接頭辞のインデックス [右境界]
- パターン文字列にのみ適用
移行公式：図を見て理解し、図中の①②に注目
- $next[i+1]=\left{\begin{aligned}&next[i]+1&t[i+1]=t[next[i]+1]\&next[next[i]]+1&t[i+1]\neq t[next[i]+1]\ &&\ t[i+1]=t[next[next[i]]+1]\&next[next[next[...[i]]]]+1&until\ equal\ or\ the\ end\end{aligned}\right.$
- 最初の 2 行、3 行を見て、①を判断する
  - もし $t [i+1]=t [next [i]+1]$ であれば、$i+1$ に対応する最長接頭辞は $next [i]+1$ である
  - そうでなければ、$t$ をできるだけ短い距離右に移動させる [上記の思考過程の④に類似]、つまり部分文字列 $t [0\to j]$ の中で、$j$ で終わる接尾辞の中で、対応する最大接頭辞を見つける [これが $next$ 配列の定義]
- 最初の 1 行、2 行を観察し、②を判断する
  - もし $t [i+1]=t [next [j]+1]$ であれば、$i+1$ に対応する最長接頭辞は $next [j]+1$ であり、ここで $j=next [i]$
  - そうでなければ、$t$ を右に移動し続け、③④... 等しい関係が満たされるまで、または $t$ がこれ以上右に移動できなくなるまで判断する
動的計画法の思想に関わる、詳細は《面接筆記アルゴリズム下》——1 再帰から動的計画法へ（上）
理解を深めるための練習
- 仮想位置を定義：-1 [どの接頭辞にもマッチしない場合、値は - 1]
- 練習 1
- 練習 2
- 答え：-1、-1、0、-1、0、1、2、3、4、5、6、1
[PS] 参考KMP アルゴリズムの詳細——CSDN
- 文中の $next$ 配列は：接頭辞と接尾辞の最大共通長さとして定義されている [文字列自体を含まない、そうでなければ最大長は常に文字列自体になる]
- $next$ 配列の定義は一意ではないことがわかる
- 自身の構造の繰り返し展開の概念、$next$ 配列を求める際にこの思想がある

マッチングプロセス#

テキスト文字列 $s$ の各位置を順番に走査する
パターン文字列 $t$ の開始位置からマッチングを開始する
1. もしテキスト文字列 $s$ の現在位置とパターン文字列 $t$ の現在位置が等しい場合、次の位置のパターン文字列 $t$ をマッチングする
2. そうでなければ、$next$ 配列に基づいてパターン文字列 $t$ のマッチング位置を前方に移動し続け、等しい条件が成立するまで、またはこれ以上前に移動できなくなるまで、テキスト文字列 $s$ の次の位置をマッチングする
パターン文字列 $t$ の末尾に成功裏にマッチングできた場合、テキスト文字列 $s$ に対応するマッチング位置を出力する；または見つからなかった場合

小結#

パターン文字列の第③部分の重要性を理解する [思考過程を参照]
- マッチング速度を加速する核心であり、大量の無駄なマッチング試行を避ける
漏れを保証する核心：第③部分がマッチングするのはパターン文字列の最長接頭辞である
状態機械の観点から理解でき、コードデモを参照 —— 状態機械版 KMP
時間計算量：$O (m + n)$
[PS] KMP にはいくつかの最適化方法も存在する

SUNDAY#

先に尻を探し、次に頭を探す

シミュレーション操作#

以下の状況を直接シミュレートする

① 不一致が発生したとき、パターン文字列 $t$ の末尾に対応する母文字列 $s$ の次の位置e——黄金の整列点
- [注意] 不一致位置の次の位置を観察すること < 図に誤解されないように >
② パターン文字列 $t$ の中で、後ろから前に最初のe の位置を探す
- 倒数第 2 位で e を見つける
③ 倒数第 2 位は、パターン文字列 $t$ が母文字列 $s$ のマッチング位置を正数 2 位右に移動させ、その後母文字列 $s$ を再度マッチングすることを意味する
- [個人的理解] この右移動が成功するためには、e の位置が整列する必要がある、なぜなら必ず e を通過するから；最初の e を探すのは、答えを漏らさないためである
④ 上の図でも不一致が発生した場合、再度パターン文字列 $t$ の中で後ろから前に最初の a を探し、整列し、マッチング... 成功するまで、またはマッチングが終了するまで
[PS] 黄金の整列点に対応する文字が見つからない場合、右移動のオフセットはパターン文字列 $t$ の長さ + 1 となる

プロセス#

各文字がパターン文字列中で最後に出現した位置を事前に処理する
ブルートフォースマッチングアルゴリズムのプロセスをシミュレートし、不一致のとき、テキスト文字列のポインタは上記の事前処理情報に基づいて、相応の位置に後方移動し、再度マッチングする
最終的に、マッチング成功時にインデックスを返すか、見つからない

小結#

核心：黄金の整列点を理解する [シミュレーション操作を参照]
- マッチングが成功すれば、必ずパターン文字列の中に存在する
- それはパターン文字列の中でその文字が最後に出現した位置と整列するべきである
右移動操作：探している文字がパターン文字列の倒数第何位に出現するかによって、テキスト文字列のポインタを右に移動させる
最速の時間計算量：$O (m /n)$
- 対応するシナリオ：探している黄金の整列点の文字がパターン文字列の中に見つからない場合、テキスト文字列のポインタはパターン文字列の長さ $n + 1$ の距離を後方移動させる
[PS]
- 最悪の時間計算量：$O (m\times n)$、しかしこのような場合の文字列は一般的に実際的な意味を持たない
- 使用シナリオ：単一の単語を文章の中で探すなどの単純な単一パターンマッチング問題 <工業で非常に一般的>
- KMP と比較
  - SUNDAY は理解しやすく、実装が簡単である
  - しかし KMP アルゴリズムの思考方法はより高度であり、学ぶべきである [状態機械]

SHIFT-AND#

非常に美しいニッチなアルゴリズム、想像力を試す
状態機械思想：NFA、非決定性有限状態オートマトン

コーディング配列 d#

⭐パターン文字列をある種のコーディングに変換し、変換後のマッチング問題はパターン文字列とは無関係になる

0 番目から始めて、パターン文字列 t の各位置を順番に読み取る
0 番目に 'a' 文字が出現した場合、$d$ 配列のインデックス 'a' の要素を 0 位置に 1 を設定する
1 番目に 'e' 文字が出現した場合、$d$ 配列のインデックス 'e' の要素を 1 位置に 1 を設定する
このようにして $d$ 配列を得る
[PS]
- $d$ 配列のインデックスは文字の ASCII コードに対応できる
- $d$ 配列の要素は int 型 [32 ビット]、long long 型またはカスタム型を保存でき、これがマッチング可能な最長パターン文字列の長さを決定する
- 文字列の順序と $d$ 配列要素の数字の順序に注意、0 番目の文字は後者の低位に対応する

状態情報 p#

状態定義を理解し、状態の移行を感じる

状態定義：$p_i$
- $p_i$ の二進数表現の中で、もし第 $j$ 位が 1 であれば、テキスト文字列 $s [i]$ で終わるとき、パターン文字列の前 $j$ 位を成功裏にマッチングできることを示す
- 図解、上記の定義と以下の 3 対の円を対照させる
  - 赤色：$p_4$ はテキスト文字列 $s [4]$で終わる、現在のマッチング条件を示す
  - オレンジ色：$p_4$ の第 2 位が 1 であることは、パターン文字列 $t$ の前 2 位が上記のマッチング条件を満たすことを示す、すなわち $t [0\to 1]$ と $s [3\to 4]$ がマッチングする
  - 緑色：$p_4$ の第 5 位が 1 であることは、パターン文字列 $t$ の前 5 位が上記のマッチング条件を満たすことを示す、すなわち $t [0\to 4]$ と $s [0\to 4]$ がマッチングする
  - [PS]
    - $p$ の二進数の長さは、使用するデータ型によって決まる、$d$ 配列の要素と同様に、int：32 ビット
    - $p_4$ がどのように得られるかは、後で移行プロセスを見てから考える
- ⭐このように見える
  - $p$ は同時に複数のマッチング結果の情報を保存している❗
  - $p_i$ の第 $n$ 位が 1 であれば、マッチング成功、すなわち
    - $p_i\ &\ (1\ <<\ (n-1))=1$
    - マッチング位置は：$i-n+1$
移行プロセス：$p_i=(p_{i-1}\ <<\ 1\ |\ 1)\ &\ d [s [i]]$
- ⭐重要な公式⭐
- この時点でパターン文字列 $t$ を完全に無視し、$p$ の前の状態と $d$ 配列を通じて、現在の $p$ の値を得ることができる
- 原理分析、重要な公式と下図の①②を対照させる
  - $p_3$ が既知で、現在 $s [2\to 3]$ と $s [0\to 3]$ がマッチングできると仮定する
  - ①左に 1 位移動+または 1 演算を行い、遷移状態 $p_4^{'}$ を得る
    - 左に 1 位移動：前のマッチングの基礎の上で $s [4]$ を飲み込もうとし、すなわち $s [2\to 4]$ と $s [0\to 4]$ がマッチングする
      - マッチング成功の条件は後の【論理積演算】にある
      - [注意] 左移動操作は図中では右移動として表現される、なぜなら数字の順序は低位が前にあるから
    - または 1 演算：$s [4]$ の単独マッチングの機会を残す、マッチング成功はこの 1 文字をマッチングすることを示す
  - ②論理積演算
    - 上記の 2 つの操作はすべてマッチングを試みるだけであり、実際の成功は $d [s_4]$ の結果に依存する
    - もし第 $j$ 位の論理積演算の結果が 1 であれば、$s [4-j+1\to 4]$ と $t [0\to j-1]$ が成功裏にマッチングすることを示す
      - 例えば $p_4 [2]=1$、$p_4 [5]=1$、マッチング結果は状態定義部分の図解に示される
[PS]
- $p$ の初期値は 0 であり、$p$ は実際には非決定性有限状態オートマトンである
- 習慣的な衝突：一般的に数字の順序の右側は低位であるが、図中の $p$ の左側は低位である；二進数の数字の最低位は 1 であり、文字列の最低位は 0 である；$d$ 配列の要素は数字であるため、数字の順序に対応するべきだが、上図はパターン文字列との対応位置関係を示すために文字列の順序を使用している
- $p$ の意味を正確に理解する：前回成功裏に 4 位をマッチングした場合、次回は 5 位を成功裏にマッチングできる可能性がある
- 64 ビットを超える文字列マッチング問題については、自分でデータ型を作成する必要がある
  - 左移動、または、または論理積演算ができるようにする
  - その後、コーディング配列 $d$ と状態情報 $p$ の型を対応して変更する

小結#

① コーディング配列 $d$：パターン文字列中の各文字の出現位置を、対応する二進数コーディングに変換する
② 状態情報 $p$：重要な公式 $p_i=(p_{i-1}\ <<\ 1\ |\ 1)\ &\ d [s [i]]$ を通じて状態を移行する
時間計算量：$O (m)$
- パターン文字列を往復する必要は全くない
- しかし厳密に言えば、純粋な $O (m)$ ではなく、これはコンピュータのデータ表現能力に関係している
❗ 正規表現マッチング問題を解決できる
- 例えば：$(a|b|c)&(c|d)&e&(f|a|b)$
- ① 上記のパターン文字列をコーディング配列 $d$ に変換する
  - $d$ 配列の各列には複数のビットを持たせ、1 に設定する
  - すなわち、パターン文字列の各位置は複数の【$d$ 配列の要素】の対応する二進数ビットを 1 に設定できる
- ② その後はパターン文字列とは無関係になり、$d$ 配列と重要な公式に基づいて問題を解決する
- [PS] ここでパターン文字列がパターン文字列と呼ばれる理由は、文字列だけでなく、正規表現も指すからである（関連性のある複数のパターンとも見なすことができる）

コードデモ#

ブルートフォースマッチング法#

2 つのバージョン、簡潔なバージョンのテクニックを学び、$flag$ を柔軟に使用する
テキスト文字列とパターン文字列をそれぞれ走査し、各位置を比較し、不一致があればテキスト文字列のポインタを 1 つ右に移動させる
この思想はすべての文字列マッチングアルゴリズムの基礎である

KMP#

2 種類のプログラミング方式、後者はアルゴリズムの本質的な思想により近い

① 通常のコーディング：$next$ 配列を直接取得し、その後 $next$ 配列を使用して不一致オフセットを行う
- $next$ 配列を事前処理→テキスト文字列の各位置を走査→パターン文字列をマッチング [利用 $next$ 配列]
- ❗ 観察：$next$ 配列を取得するプロセスとテキスト文字列をマッチングするプロセスは非常に似ており、状態機械の思想に基づいて、2 つの部分を統合できる
② 高度なプログラミング：状態機械の思想に基づき、$next$ 値を取得するプロセスを状態の変化プロセスに変換する
- 状態機械モデルを抽象化した：$j$ が指し示すのは状態機械の位置であり、$getNext$ メソッドは入力文字に基づいて状態をジャンプさせる、実際には $j$ の値を変更することに相当する
- KMP の本質的な思考方法により近い
PS：マッチング成功後に $i-n+1$ を返す前に $next$ 配列を free するべきである

SUNDAY#

❗ 256 の意味に注意：各文字がパターン文字列中で出現する位置を記録するために使用される
$offset$ 配列の事前処理プロセス：最初にすべて出現しない状態で初期化し、$n+1$ はテキスト文字列のポインタがパターン文字列の長さ + 1 の距離を直接右に移動できることを示す；事前処理の過程で、後に同じ文字が出現する位置は前の位置を上書きし、SUNDAY の意図に合致する
$s [i + n]$：黄金の整列点に対応する文字
$i + n <= m$：$n$、$m$ 変数を合理的に利用し、テキスト文字列がまだパターン文字列とマッチングできることを示す
KMP と比較して、SUNDAY は理解しやすく、コードの実装が簡単である [単純な単一パターンマッチング問題を解決するための最良の選択]

SHIFT-AND#

⭐ 思想が美しく、コードがシンプルである
注意
- 数字に関連する $d$ 配列の要素と状態 $p$ は、最低位が 1 である；一方、文字列は 0 に対応する
- しかし移行プロセスは数字間の演算であるため、位置が整列しているかどうかは気にする必要はない

課題演習#

——Hash——#

よく使われる解法のパターン

HZOJ-275：ウサギとウサギ#

サンプル入力

aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2

サンプル出力

Yes
No
Yes

思考
- 注意：クエリの回数が非常に多く、クエリ範囲が非常に大きいため、ブルートフォースマッチングは必ずタイムアウトする
- どのように迅速に比較するか？👉 ハッシュマッチングアルゴリズム
  - ハッシュ操作を通じて文字列を数字 <ハッシュ値> で表現する
  - もし 2 つの文字列に対応するハッシュ値が異なれば、2 つの文字列は必ず等しくない
    - これにより大部分の不等しい場合を排除でき、ビットごとに比較する必要がなくなる
  - そうでなければ、ブルートフォースマッチングを通じて文字列が等しいかを検証する
    - もし 2 つの文字列が等しければ、一度のマッチングで成功する
  - [PS]
    - 長い文字列に直接対応するハッシュ値は非常に大きくなる可能性があるため、一般的には剰余操作を通じてハッシュ値を縮小する
    - 余りが異なれば 👉 文字列は必ず異なる
- ハッシュ関数を設計する [文字列 -> ハッシュ値]
  - $H=(\sum_{k=0}^{n-1}{C_k\times base^k})%P$
  - $n$：文字列 $s$ の長さ
  - $C_k$：第 $k$ 位の文字に対応する ASCII コード値
  - $base$：位重み [素数]
  - $P$：モジュラス [素数]
  - [PS] 文字はコンピュータの底層で二進数の数字として保存されている
- ⭐本題における部分文字列 $s [j\to i]$ のハッシュ値 $H_{j\to i}$
  - 文字列とハッシュ値の関係に基づいて、ハッシュに基づく前方和配列を事前に処理することができる
    - $HS_i=(\sum_{k=0}^{i}{C_k\times base^k})%P$
  - したがって部分文字列 $s [j\to i]$ のハッシュ値は
    - $HS_{j\to i}=(\sum_{k=j}^{i}{C_k\times base^k})%P$
  - しかし部分文字列のハッシュ値は、文字列内の部分文字列の位置情報 $j$、$i$ を含むべきではなく、すなわち乗数因子は $base^0$ から始めるべきである
  - したがって、区間和 $HS_{j\to i}$ を $base^j$ で割る必要があるが、剰余演算に関しては直接割り算を行うことはできず、逆元を利用する必要がある
  - 最終的な部分文字列 $s [j\to i]$ のハッシュ値 $H_{j\to i}$ は次のように変換される
    - $H_{j\to i}=HS_{j\to i}\times(base^j)^{-1}%P=(HS_i-HS_{j-1})\times(base^j)^{-1}%P$
    - $(base^j)^{-1}$：$base^j$ の逆元
    - 逆元の迅速な求解については、迅速に求める [モジュール] 逆元を参照
- 解法①
  - 1. テキスト文字列上で、各位置に基づくハッシュの前方和を事前に処理し、後で区間和を求めるのを便利にする
  - 1. 区間和と逆元を通じて、特定の部分文字列 $s [i\to j]$ のハッシュ値を求める：
    - $H_{j\to i}=HS_{j\to i}\times(base^j)^{-1}%P$
  - 1. 2 つの部分文字列のハッシュ値を比較する
    - もし不等しければ、部分文字列は必ず異なる
    - そうでなければ、ブルートフォースマッチングを通じて等しいかを検証する
  - ❗ 2 つの部分文字列が異なっていても、そのハッシュ値が等しい可能性は $1/P$ である
- 解法②
  - 解法①に基づき、2 つのハッシュ関数を設計し、$P$、$base$ を異なるものにする
  - 2 つの部分文字列に対応する 2 つのハッシュ値を比較する
    - 両方が等しいとき、2 つの部分文字列が同じと認定する
    - そうでなければ、必ず異なる
  - ❗ 2 つの部分文字列が異なっていても、そのハッシュ値が等しい可能性は $1/(P_1\times P_2)$ である
    - エラーの確率は非常に低く、実際には多くのアルゴリズムが確率的アルゴリズムである
コード
- 解法①：ハッシュマッチング + ブルートフォースマッチング
- ①$P$ の値は素数でなければならず、そうでなければ一部の逆元は意味を持たず、求められたハッシュ値が正しくない
  - これにより同じ部分文字列が異なるハッシュ値に対応する可能性がある
  - 逆元が存在するための十分必要条件：互いに素であること
- ② long long 型を使用する必要があり、中間過程の数値は非常に大きくなる可能性がある
  - これにより異なる部分文字列が同じハッシュ値に対応する確率が増加し、ブルートフォースマッチングの時間が増加する
- [PS]
  - 常に剰余を取ることを忘れず、数値が表現範囲を超えないようにする、たとえ long long であっても
  - ハッシュ値が正であることを保証することに注意
    - ハッシュに基づく前方和配列 $H$ は単調増加ではない、なぜなら和を求める際に剰余操作が行われるからである
  - $P$ の値が小さすぎるとタイムアウトが発生し、ブルートフォースマッチングの回数が多くなる
- 解法②：ハッシュマッチング * 2
- 注意：2 つの逆元配列を分けて初期化し、完全に初期化されることを保証する [走査範囲が異なるため]
  - または同じ $P$ と異なる $base$ を使用して一緒に初期化することができる
- [PS] 保険のために、ブルートフォースマッチングの検証を追加することができる

迅速に求める [モジュール] 逆元#

⭐推導過程

目標：$x\times x^{-1}\equiv1\ (mod\ P)$ の中の $x^{-1}$ を求める
- [PS] $x<P$ のケースのみ考慮する、なぜなら $P$ より大きいすべての $x$ は剰余を取ることで $P$ より小さい $x$ に変換できるからである
令：$P\ %\ x=r,P\ /\ x=k$
したがって：
- $\begin{aligned}P&=kx+r\kx+r&\equiv0\ (mod\ P)\kx(x^{-1}r^{-1})+r(x^{-1}r^{-1})&\equiv0\ (mod\ P)\kr^{-1}+x^{-1}&\equiv0\ (mod\ P)\x^{-1}&\equiv-kr^{-1}\ (mod\ P)\\end{aligned}$
最終的に $x^{-1}$ を求める問題を $r^{-1}$ を求める問題に変換する
- そして $r$ は $x$ の剰余であるため、$r$ は必ず $x$ より小さい
大規模な問題 👉 小規模な問題 [再帰的]
逆元が正であることを保証するために、もう一度処理を行う
- $x^{-1}_{+}=(-kr^{-1}\ %\ P+P)\ %\ P$
[PS]
- モジュール逆元：逆元が存在するための十分必要条件は $p$ と $x$ が互いに素であること
- 逆元を求める方法は多く、逆元の知識普及 (啓蒙編)を参照 ——cnblogs

コード

モジュラスが何であれ、1 の逆元は 1 である [初期化]
出力結果
- 自分で検証できる：元の数と逆元を掛け算して剰余を取ると 1 になる

追加知識点#

KMP、SHIFT-AND の本質的な思想：状態機械 <コンパイラ原理で学ぶ知識>
SUNDAY アルゴリズムは日常生活で非常に一般的であり、Hash マッチングアルゴリズムは問題解決で一般的に使用される
DFA、NFA はコンパイラ原理の知識である
- 主な違い：DFA は速度が速く、NFA はメモリを少なく消費する
- 参考DFA と NFA の違い——Stechies

ヒント#

C++ の前に、必ず予備課程を終わらせること
アルゴリズム分野の専門家になるための鍵は、自分の美的感覚を高めることにある
怒ることは無能の表れであり、正しいことをする！一歩一歩良くなり、一気に成功を求めない