python - 找到具有共同首尾字符的最长字符串链的最快方法是什么？

Question

这个看起来很简单，但我在 Python 中实现它时遇到了麻烦。

假设你有一个长度为 2 的字符串数组：["ab","bc","cd","za","ef","fg"]

这里有两条链："zabcd"和"efg"

找到最长的最有效的方法是什么？（在这种情况下是"zabcd"）。链也可以是循环的……例如["ab","bc","ca"]（在这种特殊情况下，链的长度为 3）。

标签： python

Answer 1

这显然是一个图问题，字符是顶点，对是未加权的有向边。

在解决方案中不允许循环，这是最长的路径问题，并且它是 NP 难的，因此即使允许循环，“高效”也可能不在窗口中（为了摆脱解决方案循环，将顶点拆分为两个，一个用于输入边缘，一个用于输出边缘，中间有一个边缘）。根据维基百科，没有好的近似方案是已知的。

如果图表是非循环的，那么您可以在线性时间内完成，正如维基百科文章提到的那样：

加权图 G 中两个给定顶点 s 和 t 之间的最长路径与图 -G 中的最短路径相同，该最短路径是通过将每个权重变为其否定来从 G 导出的。因此，如果最短路径可以在 -G 中找到，那么最长路径也可以在 G 中找到。 [4]

对于大多数图，这种变换没有用，因为它在 -G 中创建了负长度的循环。但是如果 G 是有向无环图，则不能创建负循环，并且可以通过对 -G 中的最短路径应用线性时间算法在线性时间内找到 G 中的最长路径，这也是有向无环图。 [4] 例如，对于给定 DAG 中的每个顶点 v，可以通过以下步骤获得以 v 为终点的最长路径的长度：

找到给定 DAG 的拓扑排序。对于 DAG 的每个顶点 v，在拓扑排序中，通过查看其传入邻居并将这些邻居记录的最大长度加一来计算以 v 结束的最长路径的长度。如果 v 没有传入邻居，则将结束于 v 的最长路径的长度设置为零。在任何一种情况下，都要记录这个数字，以便算法的后续步骤可以访问它。一旦完成，整个 DAG 中最长的路径可以通过从记录值最大的顶点 v 开始，然后反复向后退到记录值最大的传入邻居，并反转在这边走。

还有其他一些特殊情况，可以使用有效的算法，尤其是树，但是因为您允许可能不适用于您的循环。

我没有在这里为您提供算法，但这应该为您的研究提供正确的方向。问题本身可能很简单，但有效的解决方案不是。