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

Question

定义字符串M的次数为它在另一个字符串S中出现的次数。例如M = "aba" and S="ababa"，M的次数为2。给定一组字符串和一个整数N，求最小长度的字符串，使得集合中所有字符串的度数之和至少为N。

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

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

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

Answer 1

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

我们select 从池中取出一个长度最小且度数之和=N 的字符串。如果我们找到这样的字符串，我们就 return 它。
我们从池中过滤掉度数小于最大值的所有字符串。我们只使用最佳可能的字符串组合。
我们根据当前池和初始字符串构建所有变体。这里我们需要考虑到字符串可以重叠。假设一个字符串“aba”和“ab”（来自初始字符串）可以产生：ababa、abab、abaab（我们不包括“aba”，因为我们已经在我们的池中有了它，我们需要进一步移动）。
我们过滤掉重复项，这是我们的下一个池。
从第 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);
}

Answer 2

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

首先，将集合中的每个字符串加上空字符串作为一个图的节点。空字符串相互连接，反之亦然。如果一个字符串的结尾与另一个字符串的开头重叠，它们也会连接。如果两个可以重叠不同的数量，它们就会得到多个边缘。（所以它不完全是一个图表...）

每条边都有一个 cost 和一个 value。 cost 是为了从旧端移动到新端，您必须扩展正在构建的字符串的字符数。（换句话说，第二个字符串的长度减去重叠的长度。）拥有这个。值是你完成了多少新字符串，跨越了前者和后者字符串之间的障碍。

你的例子是{"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) 问题。

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

Shortest string containing the most occurrence of strings in a set

string

algorithm

dynamic-programming

data-structures