将一组字符串匹配到一个字符串以最大化可能的匹配数

Question

我有一个非常有趣的问题。

我有一组字符串，我想知道如何最好地匹配这些字符串组合在另一个字符串对最大化函数。

就是一个例子。说我有一组：

['aabbcaa', 'bbc'] 

和我有串

'fgabbcdaabbcaaef' 

，为此可能的匹配为：

fga[bbc]daadaa[bbc]aaef 

或

fga[bbc]daad[aabbcaa]ef 

现在，给定一个简单的最大化函数，我会说t帽子fga[bbc]daad[aabbcaa]ef由于匹配的字符总数而成为赢家。一个不同的最大化函数可以给予较大的单词更多的权重，而不是总字符。

我想知道是否有人可以指示我如何做到这一点algos。我很难过是在找到一组潜在的匹配之后，我不确定如何最大限度地利用有效方式选择一组词。

字典，字典中的单词和匹配的单词可以是任意大小。

希望我能得到任何帮助。谢谢！

Answer 1

找到了答案，它很好地工作。伪代码是：

• 循环遍历集合，并在目标字符串中找到设置字符串匹配的位置。存储start_index，end_index，并为该匹配字符串提供分数。我目前使用字符串的长度。
• 然后用找到的所有比赛中，通过“权区间调度”算法运行它来寻找匹配的一组最佳
• https://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf