A longest common subsequence algorithm suitable for similar text strings |
| |
Authors: | Narao Nakatsu Yahiko Kambayashi Shuzo Yajima |
| |
Affiliation: | (1) Center for Educational Technology, Aichi University of Education, Kariya, 448 Aichi, Japan;(2) Department of Information Science, Kyoto University, 606 Kyoto, Japan |
| |
Abstract: | Summary Efficient algorithms for computing the longest common subsequence (LCS for short) are discussed. O(pn) algorithm and O(p(m-p) log n) algorithm Hirschberg 1977] seem to be best among previously known algorithms, where p is the length of an LCS and m and n are the lengths of given two strings (m n). There are many applications where the expected length of an LCS is close to m.In this paper, O(n(m-p)) algorithm is presented. When p is close to m (in other words, two given strings are similar), the algorithm presented here runs much faster than previously known algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|