string - 给定两个字符串，找到最长的公共(public)字符包

Question

这道题与那种从两个字符串中寻找最长序列或子串的题目略有不同。

给定两个大小为 N 的字符串，从每个字符串中找到最长的子字符串，使得子字符串包含相同的字符包。

两个子串不一定有相同的顺序。但它们必须具有相同的字符包。

例如，

a = ABCDDEGF b = FPCDBDAX

最长的字符匹配包是ABCDD(ABCDD来自a，CDBDA来自b)

如何解决这个问题？

---

更新

目标是从每个输入字符串中找到子字符串，以便它们具有相同的字符包。通过说“子字符串”，它们必须是连续的字符。

---

更新:最初我想到了动态规划的方法。它的工作原理如下。

要比较两个相同长度 K 的字符包，需要 O(K) 时间才能实现。将每个字符串转换为缩写形式:

ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1

缩写形式是对字母表进行排序，后跟字符串中的频率数。 构建、排序和比较缩短形式总共需要 O(K) 时间。 (虽然可以通过使用字符数组来实现)

如果两袋字符的缩写形式具有相同的字符和各自的频率，则它们相等。

此外，查找两个字符串之间的不同字符需要 O(logK) 时间。

现在，对于两个输入字符串:

1. 如果它们的缩写形式相同，则这是最长的公共(public)字符包。
2. 在 string1 中找到不出现在 string2 中的字符。根据这些字符将 string1 标记为几个子字符串。
3. 在 string2 中找到不出现在 string1 中的字符。根据这些字符将 string2 标记为几个子字符串。
4. 现在，我们有两个字符串列表。比较每一对(这又是相同的问题，但输入量较小)并找到最长的公共(public)字符包。

最坏的情况是 O(N³)，最好的情况是 O(N)。有更好的主意吗？

Answer 1

创建一组出现在 a 中的字符，以及 b 中出现的另一个字符.遍历每个字符串并删除(例如，用一些其他不可能的值覆盖)其他字符串中不在集合中的所有字符。找到每个中剩余的最长字符串(即，最长的字符串只有“未击中”的字符)。

编辑:这是一个大致如上所述的解决方案，但以一种相当特定于语言的方式(使用 C++ 语言环境/方面):

#include <string>
#include <vector>
#include <iostream>
#include <locale>
#include <sstream>
#include <memory>

struct filter : std::ctype<char> {
    filter(std::string const &a) : std::ctype<char>(table, false) {
        std::fill_n(table, std::ctype<char>::table_size, std::ctype_base::space);

        for (size_t i=0; i<a.size(); i++) 
            table[(unsigned char)a[i]] = std::ctype_base::upper;
    }
private:
    std::ctype_base::mask table[std::ctype<char>::table_size];
};

std::string get_longest(std::string const &input, std::string const &f) { 
    std::istringstream in(input);
    filter *filt = new filter(f);

    in.imbue(std::locale(std::locale(), filt));

    std::string temp, longest;

    while (in >> temp)
        if (temp.size() > longest.size())
            longest = temp;
    delete filt;
    return longest;
}

int main() { 
    std::string a = "ABCDDEGF",  b = "FPCDBDAX";
    std::cout << "A longest: " << get_longest(a, b) << "\n";
    std::cout << "B longest: " << get_longest(b, a) << "\n";
    return 0;
}

Edit2:我相信这个实现在所有情况下都是 O(N)(每个字符串遍历一次)。那是基于 std::ctype<char>使用表进行查找，这是 O(1)。使用哈希表，查找也将具有 O(1) 预期复杂度，但最坏情况为 O(N)，因此总体复杂度为 O(N) 预期，但最坏情况为 O(N²) .使用基于平衡树的集合，您总体上会得到 O(N lg N)。