鉴于两个字符串,找到最长的常见字符包

Question

这个问题与从两个字符串中找到最长序列或子字符串的类型略有不同.

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

两个子串可能不一定具有相同的序列.但他们必须拥有相同的字符包.

例如,

a = ABCDDEGF b = FPCDBDAX

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

如何解决这个问题呢？

---

UPDATE

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

---

更新:最初我想到了一种动态编程方法.它的工作原理如下.

为了比较相同长度K的两袋字符,需要O(K)时间来实现.将每个字符串转换为缩短形式:

ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1

缩短形式是按字母表排序的字母表,后跟字符串中的频率数.构造,排序和比较缩短形式总共需要O(K)时间.(虽然可以通过使用字符数组来实现)

如果两个字符的缩短形式具有相同的字符和相应的频率,则它们是相同的.

此外,需要O(logK)时间才能找到两个字符串之间的差异字符.

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

1. 如果他们的缩短形式是相同的,那么这是最常见的字符包.
2. 在string1中查找字符,使它们不出现在string2中.根据这些字符将string1标记为多个子字符串.
3. 在string2中查找字符,使它们不出现在string1中.基于这些字符将字符串2标记为多个子字符串.
4. 现在,我们有两个字符串列表.比较每一对(这与输入的较小尺寸的问题相同)并找到最长的常见字符包.

最坏的情况是O(N ³),最好的情况是O(N).有什么好主意吗？

Answer 1

创建一组存在的字符a,以及其中的另一个字符b.遍历每个字符串并敲击(例如,用一些其他不可能的值覆盖)所有不在另一个字符串集合中的字符.找到每个中剩余的最长字符串(即,只有"unstruck"字符的最长字符串).

编辑:这是一个大致如上所述的解决方案,但是以一种特定于语言的方式(使用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).