文字列中から与えられたパターンを見つけ出す文字列照合問題は，Web の情報検索やDNA 配列の特定パターンの検索に用いられるなど，幅広い応用範囲を持つ．パターンの編集に置換のみを許した近似文字列照合は，不一致を許す文字列照合と呼ばれ，単なる文字列照合より応用範囲が広く，また難易度も高い．この問題の解法として，高速フーリエ変換(FFT) を利用した高速な確率アルゴリズムが幾つか提案されている．それらは文字から数値への写像の生成方法により，写像総数と，解の推定値の分散が異なる．本稿で提案するアルゴリズムは，総写像数が理論上での最小であり，推定値の分散も小さい．String matching is the problem of finding all occurrences of a given pattern string in a given text string. It is applicable to a wide range of fields, such as Web information retrieval and pattern discovery of DNA sequences. An extension of the string matching is string matching with mismatches, which allows inexa...
