Saturday, February 21, 2009

Optimal prefix-suffix matches

You are given a finite set of string S = { s1, s2, .... sn } over a finite alphabet Σ. Two strings s1 and s2 have a prefix-suffix match if s2 has a prefix α which is a suffix of s1 (i.e. s1 = φα, s2 = αλ ). In this case the strings can be joined in a superstring φαλ and the value of this join is | α |. In this case s1 is tail-joined and s2 is head-joined. If a string is tail(head)-joined, it can not be tail(head)-joined again with other strings. Find the combination of prefix-suffix matches in S with maximum value.

No comments:

Post a Comment