如何找到字符串

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”。

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

用伪码解决方案将不胜感激。

Answer 1

现在提供改进的描述，我认为下面的算法会做：

1. 分割字符串列表成段的（串的阵列的列表）的列表
2. 开始以i = 1，增加它每次迭代执行以下操作（步骤3和4），直到有在段的列表中没有更多的项目：
3. 添加所有段阵列与长度i到列表中（如果尚未在那里）当前的解决方案和相应的最终解决方案的路径。
4. 从段的量，第一i个项目是相同的，作为在当前解决方案中的项目（然后重置当前的解决方案）中的一个的列表中删除所有项目。