包含集合中出现次数最多的字符串的最短字符串

Question

将字符串M的次数定义为它在另一个字符串S中出现的次数。例如M="aba"；并且S＝"0"；ababa"；，M的度数为2。给定一组字符串和一个整数N，找到最小长度的字符串，使该集合中所有字符串的度数之和至少为N。

例如，一个集合{"ab"，"bd"，"abd"，"babd"，"abc"}，N＝4，则答案将是"ab"；babd"；。它包含"；ab"abd"babd"；以及"；bd"；一次。

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

如何解决这个问题？这看起来类似于具有指数复杂性的动态规划解决方案的最短超弦问题。然而，这个问题的约束要大得多，同样的想法在这里也不起作用。有没有一些字符串数据结构可以在这里应用？

Answer 1

我有一个多项式时间算法，我懒得编写它。但我会为你描述的。

首先，使集合中的每个字符串加上空字符串成为图的节点。空字符串相互连接，反之亦然。如果一个字符串的末尾与另一个字符串开头重叠，它们也会连接。如果两个可以重叠不同的量，它们就会得到多条边。(所以这并不完全是一张图…)

每条边都会得到一个成本和一个值。成本是您必须扩展正在构建的字符串以从旧端移动到新端的字符数。(换句话说，第二个字符串的长度减去重叠的长度。)。值是您完成的跨越前一个字符串和后一个字符串之间障碍的新字符串数。

你的例子是{"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"->quot"：(0，0)"babd"->quot；abd"：(0，0)#重叠，但没有添加任何内容。"abc"->quot"：(0，0)

好的，所有这些都设置好了。我们为什么要这个图？

请注意，如果我们从"成本为0，值为0，然后在图中选择一条路径，该路径将构造一个字符串。它正确地说明了成本，并提供了价值的下限。该值可以更高。例如，如果你的集合是{"ab"，"bc"，"cd"，"abcd"}，那么路径"&quot-&gt"ab"->quot；bc"->quot；cd"；将导致字符串"；abcd"；成本为4，预测值为3。但该价值估计忽略了我们匹配"；abcd"；。

然而，对于任何只由集合中的子字符串组成的给定字符串，都有一条通过图的路径，该路径具有正确的开销和正确的值。(在每一个选择中，你都想选择尚未计数的最早开始匹配的字符串，并从中选择最长的字符串。这样你就不会错过任何匹配。)

所以我们把问题从构造字符串变成了构造通过图的路径。我们想要做的是建立以下数据结构：

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

填充该数据结构是一个动态编程问题。一旦填写完毕，我们就可以通过它进行追溯，找出图表中的哪条路径使我们以该成本获得了该价值。给定这条路径，我们就可以找出造成它的字符串

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

Answer 2

所以这是我的方法。在第一次迭代中，我们用初始字符串构造一个池。之后：

1. 我们从池中选择一个长度最小、度和=N的字符串。如果我们找到这样一个字符串，我们就把它返回
2. 我们从池中过滤出所有度小于maximal的字符串。我们只使用尽可能好的字符串组合
3. 我们从当前池和初始字符串中构造所有变体。在这里，我们需要考虑字符串可以重叠。说出一个字符串"aba"；以及"；ab"；(从最初的字符串)可以产生：ababa，abab，abaab(我们不包括"aba"，因为我们的池中已经有了它，我们需要进一步移动)
4. 我们过滤掉重复项，这是我们的下一个池
5. 从第1点开始重复所有操作

FindTarget()方法接受目标和作为参数。FindTarget(4)将解决示例任务。

public class Solution
{
/// <summary>
/// The initial strings.
/// </summary>
string[] stringsSet;
Tuple<string, string>[][] splits;
public Solution(string[] strings)
{
stringsSet = strings;
splits = stringsSet.Select(s => ProduceItemSplits(s)).ToArray();
}
/// <summary>
/// Find the optimal string.
/// </summary>
/// <param name="N">Target degree.</param>
/// <returns></returns>
public string FindTarget(int N)
{
var pool = stringsSet;
while (true)
{
var poolWithDegree = pool.Select(s => new { str = s, degree = GetN(s) })
.ToArray();
var maxDegree = poolWithDegree.Max(m => m.degree);
var optimalString = poolWithDegree
.Where(w => w.degree >= N)
.OrderBy(od => od.str.Length)
.FirstOrDefault();
if (optimalString != null) return optimalString.str; // We found it
var nextPool = poolWithDegree.Where(w => w.degree == maxDegree)
.SelectMany(sm => ExpandString(sm.str))
.Distinct()
.ToArray();
pool = nextPool;
}
}
/// <summary>
/// Get degree.
/// </summary>
/// <param name="candidate"></param>
/// <returns></returns>
public int GetN(string candidate)
{
var N = stringsSet.Select(s =>
{
var c = Regex.Matches(candidate, s).Count();
return c;
}).Sum();
return N;
}
public Tuple<string, string>[] ProduceItemSplits(string item)
{
var substings = Enumerable.Range(0, item.Length + 1)
.Select((i) => new Tuple<string, string>(item.Substring(0, i), item.Substring(i, item.Length - i))).ToArray();
return substings;
}
private IEnumerable<string> ExpandStringWithOneItem(string str, int index)
{
var item = stringsSet[index];
var itemSplits = splits[index];
var startAttachments = itemSplits.Where(w => str.StartsWith(w.Item2) && w.Item1.Length > 0)
.Select(s => s.Item1 + str);
var endAttachments = itemSplits.Where(w => str.EndsWith(w.Item1) && w.Item2.Length > 0)
.Select(s => str + s.Item2);
return startAttachments.Union(endAttachments);
}
public IEnumerable<string> ExpandString(string str)
{
var r = Enumerable.Range(0, splits.Length - 1)
.Select(s => ExpandStringWithOneItem(str, s))
.SelectMany(s => s);
return r;
}
}
static void Main(string[] args)
{
var solution = new Solution(new string[] { "ab", "bd", "abd", "babd", "abc" });
var s = solution.FindTarget(150);
Console.WriteLine(s);
}