Color Set Size Problem with Application to String Matching

摘要: The Color Set Size problem is: Given a rooted tree of size n with l leaves colored from 1 to m, m ≤ l, for each vertex u find the number different leaf colors in subtree at u. This formulation, together Generalized Suffix Tree data structure has applications string matching. paper gives an optimal sequential solution color set and matching including linear time algorithm finding longest substring common least k out input strings all between m. In addition, parallel solutions above problems are given. These may shed light on computational biology, such as multiple alignment problem.