文字列照合
更新日:
用語解説
文字列照合は、文字列の中から、指定したパターンと同じ並びの部分を探す処理です。パターンマッチングとも呼ばれます。
■ 試験で押さえるポイント
単純な方法では、各開始位置から1文字ずつ比べ、合わなければ開始位置を1つ進めます。
対象の長さがn、パターンの長さがmなら、開始位置の候補はn−m＋1個です。
KMP法やBM法は、比較の結果を利用して開始位置を大きく進め、比較回数を減らします。
■ 選択肢での判断ポイント
科目Bでは、二重ループの添字をたどり、比較回数や一致位置を求めます。
例: 対象ABABCAでパターンABCを探すと、開始位置3で一致します。