Search code examples
stringalgorithmsubstringlongest-substring

How to find all common longest substrings of a list of strings

I have a list of strings for which I need to find ALL common unique substrings (actually paths) with minimal length in them. Example:

/a/b/c

/a/b

/a

/d/e/f

/d/e

/g/h

For this input, I need the following result:

/a

/d/e

/g/h

As you see, I need the paths (or substrings) with the minimal length that have a unique prefix. /a is the minimal substring for all paths starting with /a. /d/e is the minimal substring for all paths starting with /d/e. The same goes for /g/h.

A practical application of this is to find all roots of the path trees that have a certain file in it to analyze them further. Consider this example:

/a/b/c/index.html

/a/b/index.html

/a/index.html

/d/e/f/index.html

/d/e/index.html

/g/h/index.html

Let's say I want to have the topmost (in terms of the root) paths that contain an index.html file. As a result, I want "/a/index.html", "/d/e/index.html" and "/g/h/index.html".

Any ideas? There is a lot of theory and examples for the "simple" longest common substring problem, but I have not yet found a solution for finding ALL the common longest substrings efficiently.

A solution with pseudo code would be highly appreciated.

Solution

  • Now with the improved description I think the following algorithm will do:

    1. Split the list of strings into a list of segments (list of array of string)
    2. Start with i = 1 and increase it every iteration doing the following (step 3 and 4) until there are no more items in the list of segments:
    3. Add all segment arrays with length i to the list (if not already in there) of current solutions and the corresponding paths to the final solution.
    4. Remove all items from the list of segments for which the first i items are the same as for one of the items in the current solution (then reset the current solution).