文字列の集合上の確率分布に対して，この分布の特徴を表現するような文字列として中央文字列が定義されている．中央文字列は文字列間の距離の定義に依存し，レーベンシュタイン距離が様々な研究分野での主要な道具となっている．この距離のもとで中央文字列を求める問題はNP困難として知られており，整数線形計画法による解法が提案されている．一方で拡張ハミング距離のもとでの中央文字列は多項式時間で求解できる．本研究では，レーベンシュタイン距離での中央文字列を求めるために，拡張ハミング距離での中央文字列を利用した制約式を加えることで解候補を抑制し，最適解を求める時間の短縮を目指す．