次のような単語のリストがあります。
mmad
mmaaddd
bbad
bbaadddd
ある辞書によると、mad と bad が有効な単語と見なされているとします。これらのスペルミスの一致を見つけるための理想的なアルゴリズムまたはデータ構造はありますか? トライが役立つと思っていましたが、有効な単語リスト/辞書が数千の単語で構成されている場合、それがどのように機能するかはわかりませんでした。
編集: 私は文字の観点から単語が払拭されることを心配していないことを言及する必要があります. レーベンシュタイン距離と LD 距離の方が適していると思います。この問題はその奇妙なサブセットです。