string - 如何查找字符串列表的所有常见最长子字符串

Question

我有一个字符串列表，我需要找到所有常见的唯一子字符串（实际上是路径），其中的长度最小。例子：

/a/b/c

/a/b

/a

/d/e/f

/d/e

/g/h

对于这个输入，我需要以下结果：

/a

/d/e

/g/h

如您所见，我需要具有唯一前缀的最小长度的路径（或子字符串）。/a 是所有以 /a 开头的路径的最小子字符串。/d/e 是所有以 /d/e 开头的路径的最小子字符串。/g/h 也是如此。

一个实际应用是找到路径树的所有根，其中包含某个文件以进一步分析它们。考虑这个例子：

/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

假设我想要包含 index.html 文件的最顶层（就根而言）路径。结果，我想要“/a/index.html”、“/d/e/index.html”和“/g/h/index.html”。

有任何想法吗？“简单”最长公共子串问题有很多理论和例子，但我还没有找到有效找到所有常见最长子串的解决方案。

非常感谢带有伪代码的解决方案。

score 0 · Accepted Answer

现在有了改进的描述，我认为以下算法可以做到：

将字符串列表拆分为段列表（字符串数组列表）
从 i = 1 开始，并在每次迭代中增加它，执行以下操作（步骤 3 和 4），直到段列表中不再有项目：
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.
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).

1 回答 1