The string merging problem |
| |
Authors: | Stephen Y Itoga |
| |
Institution: | (1) Department of Information and Computer Science, University of Hawaii, 96822 Honolulu, HI |
| |
Abstract: | The string merging problem is to determine a merged string from a given set of strings. The distinguishing property of a solution is that the total cost of editing all of the given strings into this solution is minimal. Necessary and sufficient conditions are presented for the case where this solution matches the solution to the string-to-string correction problem. A special case where deletion is the only allowed edition operation is shown to have the longest common subsequence of the strings as its solution.This research was supported by the U.S. Army Research Office. |
| |
Keywords: | String modification string matching editing costs of editing longest common subsequence shortest common supersequence |
本文献已被 SpringerLink 等数据库收录! |