有限オートマトンの文字列マッチャー

Question

私は、Javaを使用してFA文字列マッチャーを構築しようとしています。私は次の擬似コードを持っています。遷移関数を動作する有限オートマトン - マッチャーアルゴリズムについて

計算されなければなりません。次のアルゴリズムであるCompute-Transition-Functionは、与えられたパターンPとアルファベットのシグマを計算します。上記のコードで

分（M + 1、Q + 2）から来た場合、私は理解できませんでした。 （私はなぜk = min（m、q + 1）の代わりにk = min（m + 1、q + 2）であるのか理解しましたが、最初にmとq + 1の最小値が必要な理由）

5-7の行の間に、PkがPqaの接尾辞になるまでkを1減らしますが、Pqaの意味を理解できませんでした。

また、8行目をJavaコードに変換するにはどうすればよいですか？二次元配列で十分か、別のデータ構造が必要か

関連する質問：内部反復までのループでstring matching with finite automata

Answer 1

たちはPqを=「abdab」と文字列を持っていると言う「abdabcd」であり、そして私たちのアルファベットがABCDであり、我々はすべてのための最善の選択肢を探していますアルファベットの記号を入力し、新しい状態に遷移します。上記の場合、 'a'によって、最初に 'b'を始めに、cを引き延ばし、dシンボルは最初の文字列の3番目のシンボルへのポインタを格納する必要があります。だから、PqaはアルファベットからPqプラス文字aとして読むべきです。

私たちが1ステップ前進したいので、なぜ（q + 2とm + 1）のminが必要なのかを編集します。また、文字列の長さを制限したいと思います。なぜ私たちはq + 3、+4を実行できませんか？これは1文字だけを追加するためで、qからq + 2、+ 3までの最善の一致を1文字で拡張することはできません。