A-1アルゴリズム・プログラミング · アルゴリズム
文字列処理のアルゴリズム
String Processing Algorithm
もじれつしょりのあるごりずむ
文字列の検索、照合、置換、比較などを行うアルゴリズム。長い文字列の中から特定のパターンを探す文字列照合では、1文字ずつずらして比べる力まかせ法のほか、不一致の情報を使ってずらす幅を大きくするKMP法やBM法がある。
共有:
Related
関連キーワードの用語
A-1ポリモーフィック型マルウェア
感染や複製のたびに自身のコードを異なる鍵で暗号化するなどして外見を変化させ、パターンマッチングによる検知を逃れるマルウェア。暗号を解く復号ルーチンは変わらないため、そこを手掛かりにしたり、実行時の振る舞いを調べたりして検知する。
FE正規表現
文字列のパターンを表現するための記法。特殊文字（メタキャラクタ）を使って文字列の検索・置換・抽出を行う。正規言語に対応し、有限オートマトンで認識できる。
PD-DKMP法（クヌース・モリス・プラット法）
文字列の中からパターンを探す文字列探索のアルゴリズム。パターンを前処理して、不一致が起きたときにパターンをどこまでずらせるかを表す表（失敗関数）を作っておき、すでに一致した部分の情報を使って比較をやり直さずに進む。テキスト上の比較位置を後戻りさせないので、テキスト長n、パターン長mのとき最悪でもO(n＋m)で探索できる。