在开发模拟器的一部分时，我遇到了以下问题。考虑一个长度为n的字符串，以及这个字符串的m个子字符串，每个子字符串都有一个非负的分数。特别值得注意的是满足以下要求的子字符串集：
它们不重叠。
他们的总得分（为简单起见，总计）是最大的。
它们横跨整根弦。
我理解天真的蛮力解决方案是O（m*n ^ 2）复杂度。虽然这个算法的实现可能不会对整个项目的性能造成太大的影响（不在关键路径附近，可以预先计算等等），但它确实不适合我。
我想知道这个问题是否有更好的解决方案，如果有，它们是什么？指向相关代码的指针总是很受欢迎的，但是仅仅是算法描述也可以。
最佳答案
这可以被认为是通过DAG找到最长的路径。字符串中的每个位置都是一个节点，每个子字符串匹配都是一条边。您可以通过归纳法简单地证明，对于最优路径上的任何节点，最优路径从开始到该节点以及从该节点到结束的连接都与最优路径相同。由于这一点，您只需跟踪每个节点的最佳路径，并确保在开始考虑包含该节点的路径之前访问了该节点中结束的所有边。
然后，您只需要找到从节点开始的所有边，或在给定位置匹配的所有子字符串。如果您已经知道子字符串匹配的位置，那么它就像构建哈希表一样简单如果不这样做，那么如果使用Rabin-Karp，您仍然可以构建一个哈希表。
请注意，您将仍然访问DAG中所有的O（E）复杂度的边缘。或者换言之，您必须考虑从开始到结束在一系列连接的子串中每个子串匹配一次。通过对子字符串进行预处理，找出排除某些匹配项的方法，可以获得比这更好的结果。我怀疑是否有任何一般情况下的复杂性改进可以来此，任何实际的改进很大程度上取决于您的数据分布。