Shortest Matching of String Sequences Problem

DOI

Bibliographic Information

Other Title
  • 文字列シーケンス最短マッチング問題

Abstract

The distance between two string sequences of the same size is defined. It derives the shortest matching of string sequences problem, that is, for two string sequences S and T, the problem of finding T' with T integrated to the same size as S such that the edit distance between S and T' is minimized. In this problem, algorithms for finding the optimal solution by dynamic programming and approximate solutions by greedy ways are proposed. Since this problem with move operations of subsequences of T is NP-complete, an algorithm is proposed to solve the problem in polynomial time under some assumptions.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top