logo标签列表

给定两个字符串，找出它们最长的公共字符序列。

stringalgorithm
13

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

给定两个长度相同为 N 的字符串，查找它们各自最长的子字符串，使得这些子字符串包含相同的字符集。

这两个子字符串不一定有相同的顺序，但必须具有相同的字符集。

例如,

a = ABCDDEGF b = FPCDBDAX

最长匹配的字符集为 ABCDD（a 中的 ABCDD 和 b 中的 CDBDA）。

如何解决这个问题？

更新：

目标是从每个输入字符串中找到子字符串，使得它们具有相同的字符集。所谓“子字符串”，它们必须是连续的字符。

更新： 最初我考虑了一种动态规划的方法。其过程如下。

为了比较两个长度为 K 的字符集，需要花费 O(K) 时间。将每个字符串转换成一个简化形式：

ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1
简化形式是按字母顺序排列，然后是字符在字符串中出现的次数。构建、排序和比较简化形式总共需要O(K)时间。（可以使用字符数组来实现）
当且仅当两个字符包含相同字符及其对应频率时，它们的简化形式相等。
此外，查找两个字符串之间不同字符的所需时间为O(logK)。
现在考虑两个输入字符串：
1. 如果它们的简化形式相同，则这是最长公共字符包。 2. 查找字符串1中没有出现在字符串2中的字符。基于这些字符将字符串1标记成多个子字符串。 3. 查找字符串2中没有出现在字符串1中的字符。基于这些字符将字符串2标记成多个子字符串。 4. 现在我们有了两个字符串列表。比较每一对字符串（这又是一个具有更小输入规模的相同问题）并找到最长公共字符包。
最坏情况下的时间复杂度为O(N³)，最好情况下为O(N)。是否有更好的方法呢？
@Kobi：Chars是有范围的整数。例如，ASCII在0-128范围内。允许Unicode字符会更加棘手。我们需要频率计数来测试两个缩短形式的“相等性”。 - SiLent SoNG
@Kobi：最初，这两个输入字符串具有相同的长度。在标记化之后，我们可能会面对两个长度不同的字符串...你是正确的。我正在考虑解决您的问题的方案。 - SiLent SoNG
@SiLent SoNG：面试官有没有提到这种算法实际上在哪里使用？ - Lazer
@Lazer：这不是我的面试问题。我是从最近尝试过的朋友那里得到的。 - SiLent SoNG
这个问题能否打上“字符串”标签？ - eeerahul
显示剩余3条评论
4个回答
6
创建一个包含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;
}

编辑2：我相信这个实现在所有情况下都是O（N）的（每个字符串遍历一次）。这基于std::ctype<char>使用查找表进行查找，其复杂度为O（1）。使用哈希表进行查找也会有O（1）的预期复杂度，但最坏情况下为O（N），因此总体复杂度为O（N）的预期复杂度，但最坏情况下为O（N2）。如果基于平衡树的集合，总体复杂度将为O（N lg N）。

2
如果几乎没有（或者根本没有）不可能的字符怎么办？你所“剩下”的问题和原来一样严重，而且你还没有为那部分提出解决方案。 - Ether
1
我会进行排序和遍历，在非匹配时推进第二个索引并在匹配时存储和推进两个索引。尤其是因为两个数组的长度相同。 - Jason Coco
1
假设你有以下字符（x不可能存在）： X = xxBABAxx Y = xAxBBxAx 最长的字符串是1，即'A'或'B'。 看起来你的算法会返回'BB'。 - Déjà vu
1
@Jerry：是的，但 ABCDD 字母和 CDBDA 字母都在同一个“袋子”中作为连续字母出现。而 BB 在任何 BABA“袋子”中都找不到。换句话说，从字符串 X 中取一个连续字母的袋子，从字符串 Y 中取一个袋子，如果至少有一个 X 的排列是 Y，则它们“匹配”。这就是我理解问题的方式。 - Déjà vu
1
必须减1，因为您忽略了袋子中元素的“频率”组件。 “袋子”是一个正确的数学术语，意思与“多重集合”相同--即每个元素都带有计数/多重性/频率，并且根据我对问题的解释，这些计数需要匹配。 我认为您正在回答一个略有不同的问题，其中“袋子”已被替换为“集合”，这使问题变得更容易。 - j_random_hacker
显示剩余8条评论
4

提醒一下，这个问题不会接受“贪心”解决方案，即通过一次添加一个元素扩展现有可行包来构建越来越大的包。原因是，即使存在长度为k的可行包，也不一定存在长度为(k-1)的可行包，如下面的反例所示：

ABCD
CDAB

显然，这两个字符串有一个长度为4的包（A:1, B:1, C:1, D:1），但没有共享的长度为3的包。 这提示我问题可能相当难。

糟糕！我一直在考虑贪心算法，但你表明它行不通。如果没有贪心算法，似乎无法在O(n!)的运行时间内得出答案。 - Loren Pechtel
好吧，总有一种O(n^4)的暴力方法，将A的每个子字符串与B的每个子字符串进行比较。还可能有我没有看到的分治或动态规划方法。此外，我相当确定对于小字母表（例如二进制），应该可以找到更快的解决方案。很想再考虑一下，但现在我得做些真正的工作了！ :) - j_random_hacker
2
让我们这样看待这个问题... 这个解决方案将更加优化，编码也很容易，但是您必须阅读def并且必须阅读代码才能理解...否则它听起来只是疯狂和复杂的。 思考一下 在您的问题中，您提供了两个示例字符串，让我们将它们视为两个集合，即 {x，y，z}，由字符组成...
而且...而且...您的结果子字符串（集）将是两个字符串（集）中共同的字符，并且将是连续条目，符合条件的子字符串（ser）将具有最高数量的条目。
以上是结果的一些属性，但仅在使用以下算法/方法时有效。
我们有两个集合
a = { BAHYJIKLO }
b = { YTSHYJLOP }
取
a U b = { - , - , H , Y , J , - , - , L , O }
b U a = {Y , - , - , H , Y , J , L , O , -}
我只是用"-"或任何特殊/忽略的字符替换了未符合联合集的字符。
这样做后，我们有两个字符串，可以轻松提取HYJ，LO，Y，HYJLO 现在字符串/子字符串比较和不同的处理需要时间，因此我将这些字符串/子字符串写入以空格或不同行分隔的文本文件中... 这样当我读取文件时，我可以获得整个字符串，而不是嵌套循环来定位子字符串或管理临时变量。
在您拥有HYJ，LO，Y，HYJLO之后，我认为找到所需的结果不是问题... 注意：如果您开始使用临时变量和嵌套循环在此处理字符串和子字符串，则其解决方案将非常昂贵... 您必须像这样使用文件。
char a[20], b[20]; //a[20] & b[30] are two strings
cin>>a; cin>>b;
int t=0;

open a temporary text file "file1" to write '(built-in-function works here)'
//a U b
for(int x=0; x<length(a); x++)
{
    t=0;

    for(int y=0; y<length(b); x++)
       { if( a[x] == b[y]) t=1; }

    if(t == 1)
       { 
          write 'a[x]' to the file1 '(built-in-function works here)'
          t=0;
       }
    else
       write a 'space' to the file1 '(built-in-function works here)'
}

//b U a
for(int x=0; x<length(a); x++)
{
    t=0;

    for(int y=0; y<length(b); x++)
       { if( b[x] == a[y]) t=1; }

    if(t == 1)
       {
         write 'a[x]' to the file1 '(built-in-function works here)'
         t=0;
       }
    else
       write a 'space' to the file1 '(built-in-function works here)'
}
/*output in the file wil be like this
_____FILE1.txt_____
  HYJ  LO Y HYJLO        
*/
//load all words in an array of stings from file '(built-in-function works here)'

char *words[]={"HYJ","LO","Y","HYJLO"};
int size=0,index=0;

for( int x=0; x<length(words); x++)
    for( int y=0; x<length(words); y++)
    {
       if( x!=y && words[x] is a substring of words[y] ) // '(built-in-function works here)'
          {
               if( length(words[x] ) < size )
               {
                     size = length(words[x];
                     index = x;
               }
          }
    }

 cout<< words[x]; 
 //its the desired result.. its pretty old school bu i think you get the idea

}

我写了相关的代码... 如果你需要，给我发邮件，我会把它发送给你... 顺便说一句，我喜欢这个问题，这个算法的复杂度是3n平方。

P.S. 这里有很多伪代码，内置函数就派上用场了...我写的是 TC++ 代码... - Moon
附注2：我使用这种文件处理方法仅用两个循环完成了C ++的词法分析...因此，我的解决方案对于C ++的词法分析的复杂度为2n :) - Moon
提示：（第三部分）在面试问题时，最好解释一个算法或技术，而不是用一大堆内置函数的列表来解决问题。 - Moon
我觉得我最后一部分做错了...当单词在文件中时...最长的是所需的... - Moon
1
这是我的实现，虽然不太符合 Python 风格，但仍然利用了 Python 神奇的内置集合和字符串功能。
a = 'ABCDDEGF'
b = 'FPCDBDAX'

best_solution = None
best_solution_total_length = 0

def try_expand(a, b, a_loc, b_loc):
    # out of range checks
    if a_loc[0] < 0 or b_loc[0] < 0:
        return
    if a_loc[1] == len(a) or b_loc[1] == len(b):
        return


    if set(a[a_loc[0] : a_loc[1]]) == set(b[b_loc[0] : b_loc[1]]):
        global best_solution_total_length, best_solution
        #is this solution better than anything before it?
        if (len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]])) > best_solution_total_length:
            best_solution = (a_loc, b_loc)
            best_solution_total_length = len(a[a_loc[0] : a_loc[1]]) + len(b[b_loc[0] : b_loc[1]])


    try_expand(a, b, (a_loc[0]-1, a_loc[1]), (b_loc[0], b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]+1), (b_loc[0], b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0]-1, b_loc[1]))
    try_expand(a, b, (a_loc[0], a_loc[1]), (b_loc[0], b_loc[1]+1))


for a_i in range(len(a)):
    for b_i in range(len(b)):
        # starts of the recursive expansion from identical letters in two substrings
        if a[a_i] == b[b_i]:
            # if substrings were expanded from this range before then there won't be an answer there
            if best_solution == None or best_solution[0][0] > a_i or best_solution[0][1] <= a_i or best_solution[1][0] > b_i or best_solution[1][1] <= b_i:
                    try_expand(a, b, (a_i, a_i), (b_i, b_i))


print a[best_solution[0][0] : best_solution[0][1]], b[best_solution[1][0] : best_solution[1][1]]

忘了提到这显然是一种相当暴力的方法，我相信有一种算法可以运行得更快。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接