包含一组中出现次数最多的字符串的最短字符串

学习数学:

将字符串的度数M定义为它在另一个字符串S中出现的次数。例如M =“ aba”和S =“ ababa”,则M的度数为2。给定一组字符串和整数N,找到最小长度的字符串,以使集合中所有字符串的度数总和至少为N。

例如,一组{“ ab”,“ bd”,“ abd”,“ babd”,“ abc”},N = 4,答案将是“ babd”。它一次包含“ ab”,“ abd”,“ babd”和“ bd”。

N <= 100,M <= 100,集合中每个字符串的长度<=100。集合中的字符串仅由大写和小写字母组成。

如何解决这个问题呢?这看起来与最短的超字符串问题相似,后者具有具有指数复杂度的动态编程解决方案。但是,此问题的约束要大得多,并且同样的想法在这里也行不通。是否可以在此处应用某些字符串数据结构?

btilly:

我有一个多项式时间算法,我懒得编写代码。但我会为您描述。

首先,使集合中的每个字符串加上空字符串成为图的节点。空字符串彼此连接,反之亦然。如果一个字符串的结尾与另一个字符串的开头重叠,它们也将连接。如果两个可以重叠的量不同,则它们将具有多个边缘。(因此,它并非完全是图形...)

每条边都有成本价值费用是你有多少个字符来扩展你是从旧的结束移动到新的终端建设的字符串。(换句话说,第二个字符串的长度减去重叠的长度。)是您完成了多少个新字符串,它们越过前者和后者之间的障碍。

您的示例为{“ ab”,“ bd”,“ abd”,“ babd”,“ abc”}。这是(cost, value)每个转换对。

 from  ->   to  : (value, cost)
 ""    ->   "ab": (    1,    2)
 ""    ->   "bd": (    1,    2)
 ""    ->  "abd": (    3,    3) # we added "ab", "bd" and "abd"
 ""    -> "babd": (    4,    4) # we get "ab", "bd", "abd" and "babd"
 ""    ->  "abc": (    2,    3) # we get "ab" and "abc"
 "ab"  ->     "": (    0,    0)
 "ab"  ->   "bd": (    2,    1) # we added "abd" and "bd" for 1 character
 "ab"  ->  "abd": (    2,    1) # ditto
 "ab"  ->  "abc": (    1,    1) # we only added "abc"
 "bd"  ->     "": (    0,    0) # only empty, nothing else starts "bd"
"abd"  ->     "": (    0,    0) 

“ babd”->“”:(0,0)“ babd”->“ abd”:(0,0)#重叠,但未添加任何内容。“ abc”->“”:(0,0)

好的,所有这些都已设置。我们为什么要这张图?

请注意,如果我们以成本为0且值为0的“”开始,则采用遍历该图的路径,该路径构成一个字符串。它正确说明了成本,并提供了一个下限。该值可以更高。例如,如果您的集合是{“ ab”,“ bc”,“ cd”,“ abcd”},则路径“”->“ ab”->“ bc”->“ cd”将导致字符串“ abcd” ”的成本为4,预测值为3。但是,该价值估算缺少我们匹配“ abcd”的事实。

但是,对于仅由集合中的子字符串组成的任何给定字符串,都有一条通过图的路径,该路径具有正确的成本和正确的值。(在每个选择中,您都希望选择尚未计数的最早的起始匹配字符串,而其中选择最长的匹配字符串。这样您就永远不会错过任何匹配项。)

因此,我们已将问题从构造字符串转变为通过图形构造路径。我们要做的是建立以下数据结构:

for each (value, node) combination:
    (best cost, previous node, previous value)

填充该数据结构是一个动态编程问题。一旦填写完毕,我们就可以追溯到它,以找到图中的哪条路径以该成本使我们达到了该值。在此路径下,我们可以找出执行此操作的字符串。

有多快?如果我们的集合中有K字符串,那么我们只需要填写K * N值,就可以为每个值提供最多的K新值候选。这使得寻找O(K^2 * N)问题的道路

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

如何计算Java字符串中出现序列的次数?

如何计算一组字符串的最短唯一前缀?

如何计算字符串中出现字符串的次数(重叠)

在Excel中,如何计算子字符串在一组文本单元格中出现的次数?

查找字符串中出现次数最多的字母,然后仅打印字母,而不是计数

查找哪个字符出现在字符串中的次数最多

大熊猫:获取组中出现次数最多的字符串值

使用SQL搜索字符串中出现次数最多的值

查找子字符串在字符串中连续出现的次数最多

使用powershell在.txt文件中查找出现次数最多的字符串

从包含python中句子的字符串中找到重复次数最多的单词

查找字符串中出现次数最多的字符

如何找到列表中出现次数最多的两个字符串?

搜索一组字符串包含Java中ArrayList中的特定字符串

搜索出现次数最多的字符串

如何找到字符串中重复次数最多的单词?

数数 字符串中出现char的次数

打印一组包含特定字符串的行

如何选择关键字匹配次数最多的字符串?

LINQ查询以查找重复次数最多的多维数组的字符串

查找字符串中出现次数最多的字符

计算某些字符串在 Python 中出现的次数

如果包含在一组字符串中,则匹配字符串的 Pythonic 方法

Excel公式返回字符串在列中出现的次数

字符串和子字符串以及子字符串在主字符串中出现的次数

检查字符串是否包含一组其他字符串

如何生成一组最多 6 位的特定字符串值?

查找字符串中重复次数最多的单词

给定字符串中出现次数最多的词

TOP 榜单

热门标签

归档