1.7.8 Longest Common Substring

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A set S of strings S_1,...,S_n .

Problem: What is the longest string c such that for each S_i , 1 \leq i \leq n , the characters of c appear as a scattered subsequence of S_i ?

Implementations

  • CAP -- Contig Assembly Program (C) (rating 8)
  • Combinatorica (Mathematica) (rating 2)

    Related Problems

  • Approximate String Matching
  • Shortest Common Superstring
  • Suffix Trees and Arrays

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .