文字列照合

文字列照合は、対象文字列の中から検索文字列（パターン）と同じ並びを探し、一致する先頭位置や個数を求める処理です。文字列検索又はパターンマッチングとも呼ばれます。

■ 試験で押さえるポイント

• 単純法では候補となる各開始位置から文字を順に比較し、不一致なら開始位置を一つ進めます。配列添字と検索可能な最終位置に注意します。

• 対象長をn、パターン長をmとすると、開始候補は通常$n-m+1$個で、$m>n$なら一致候補はありません。

• KMP法はパターン自身の一致情報、Boyer-Moore系は末尾側からの比較などを利用して、不要な比較を減らします。

• 大文字・小文字、全角・半角、文字コード、正規化、重なりを許すかによって一致結果が変わるため仕様を確認します。

■ 選択肢での判断ポイント

二重ループの添字をトレースし、比較回数、一致位置、ループ終了条件を求める科目B問題に備えます。

例: 対象ABABCA、パターンABCでは、開始位置1は3文字目で不一致、開始位置3でABCが一致します。