1

给定一个字符串说S长度m 和一组其他R长度都等于或大于的字符串m。查找集合中具有S子序列的字符串。

因此，如果S是blr并且字符串集是：

bangalore
booleer
bamboo

它应该返回前两个字符串。

我知道我可以 在时间复杂度 O(n+m)中找到一个S长度字符串m是否是其他T长度字符串的子序列。n所以我知道我可以对集合中的每个元素执行此算法，但这将是 O(k*(n+m)) 的时间复杂度，k即集合的大小（并假设所有字符串都具有相同的长度）。这让我想知道是否有某种预处理可以帮助我用多个字符串解决这个问题。

那么，有什么预处理或结构可以用来解决这个问题吗？我能达到的最佳时间复杂度是多少？有没有其他方法可以解决这个问题？

4

2 回答 2

0

我没有代码实现，但我确实找到了WJ Hsu 和 MW Du于 1984 年发表的一篇论文“计算一组字符串的最长公共子序列” 。

他们的结论是，通过进行 O(L) 预处理时间（其中 L 是集合中所有字符串的总长度），可以在 O(P) 中执行每次搜索，其中 P 是针的次数出现在干草堆中。

于 2017-06-15T17:18:41.097 回答
0

对于两个字符串 ch 和 s，如果您想查找 ch 是否在以 S 作为子序列的集合中，算法将具有复杂度 O(n)

 public  bool function(string ch, string s)
        {
            if (ch.Length < s.Length)
                return false;

            int j = 0;
            for (int i = 0; i < ch.Length; i++)
            {
                if (ch[i] == s[j])
                {
                    j++;
                    if (s.Length == j)
                    {
                        return true;
                    }
                }
            }
            return false;
        }

之后，您必须将它应用于 R 中的所有字符串

于 2016-06-02T09:00:53.390 回答