Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment