求 'n' 个二进制串中最长公共子串的长度

Question

我得到 n 个字符串（n>=2 和 n<=4），每个字符串仅使用 2 个字母构成：a 和 b。在这组字符串中，我必须找到所有字符串中存在的最长公共子字符串的长度。保证存在解决方案。让我们看一个例子：

n=4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab

The result is 5 (because the longest common substring is "aaaab").

我不需要打印（甚至不知道）子字符串，我只需要打印它的长度。

还规定了结果不能大于60，即使每个字符串的长度可以高达13 000.

我尝试的是：我找到给定字符串中任意字符串的最小长度，然后将其与 60 进行比较，我选择两者之间的最小值作为 starting point。然后我开始取第一个字符串的序列，第一个字符串的每个序列的长度是len，其中len取值从starting point到1。在每次迭代中，我都会获取长度为 len 的第一个字符串的所有可能序列，并将其用作 pattern。使用 KMP 算法（因此，O(n+m) 的复杂性），我遍历所有其他字符串（从 2 到 n）并检查是否在字符串 pattern 中找到=30=]。每当找不到它时，我都会中断迭代并尝试长度为 len 的下一个可用序列，或者，如果没有，我会减少 len 并尝试所有长度与新序列相同的序列, 减少值 len。但如果它匹配，我停止程序并打印长度 len，因为我们从最长的可能长度开始，每一步递减，我们找到的第一个匹配代表最大可能的长度是合乎逻辑的。这是代码（但这并不重要，因为这种方法不够好；我知道我不应该使用 using namespace std 但它并没有真正影响这个程序，所以我没有费心）：

#include <iostream>
#include <string>
#define nmax 50001
#define result_max 60

using namespace std;

int n,m,lps[nmax],starting_point,len;
string a[nmax],pattern,str;

void create_lps() {
    lps[0]=0;
    unsigned int len=0,i=1;
    while (i < pattern.length()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len-1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

bool kmp_MatchOrNot(int index) {
    unsigned int i=0,j=0;
    while (i < a[index].length()) {
        if (pattern[j] == a[index][i]) {
            j++;
            i++;
        }
        if (j == pattern.length()) {
            return true;
        }
        else if (i<a[index].length() && pattern[j]!=a[index][i]){
            if (j != 0) {
                j = lps[j-1];
            }
            else {
                i++;
            }
        }
    }
    return false;
}

int main()
{
    int i,left,n;
    unsigned int minim = nmax;
    bool solution;
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>a[i];
        if (a[i].length() < minim) {
            minim = a[i].length();
        }
    }

    if (minim < result_max) starting_point = minim;
    else starting_point = result_max;

    for (len=starting_point; len>=1; len--) {
        for (left=0; (unsigned)left<=a[1].length()-len; left++) {
            pattern = a[1].substr(left,len);
            solution = true;
            for (i=2;i<=n;i++) {
                if (pattern.length() > a[i].length()) {
                    solution = false;
                    break;
                }
                else {
                    create_lps();
                    if (kmp_MatchOrNot(i) == false) {
                        solution = false;
                        break;
                    }
                }
            }
            if (solution == true) {
                cout<<len;
                return 0;
            }
        }
    }
    return 0;
}

事情是这样的：程序运行正常并且给出了正确的结果，但是当我在网站上发送代码时，它给出了 'Time limit exceeded' 错误，所以我只得到了一半的分数。

这让我相信，为了以更好的时间复杂度解决问题，我必须利用字符串的字母只能是 a 或 b，因为它看起来像一个我没用过的大东西，但我不知道我究竟可以如何使用这些信息。如果有任何帮助，我将不胜感激。

Answer 1

答案是分别构建所有字符串的后缀树，然后将它们相交。后缀树就像同时包含一个字符串的所有后缀的 trie。

为固定字母构建后缀树是 O(n) 和 Ukkonen's algorithm。（如果你不喜欢那个解释，你可以使用 google 找到其他的。）如果你有 m 棵大小 n 的树，现在是时间 O(nm)。

相交后缀树是并行遍历它们的问题，只有当你能在所有树中走得更远时，才走得更远。如果您有 m 棵大小为 n 的树，此操作可以在不超过 O(nm).

的时间内完成

这个算法的总时间是时间O(nm)。考虑到只读取字符串是时候了 O(nm)，没有比这更好的了。

添加少量细节，假设您的后缀树写为每个节点一个字符。所以每个节点只是一个字典，其键是字符，其值是树的其余部分。因此，对于我们的示例，对于字符串 ABABA，https://imgur.com/a/tnVlSI1 处的图表将变成类似（见下文）的数据结构：

{
    'A': {
        'B': {
            '': None,
            'A': {
                'B': {
                    '': None
                }
            }
        }
    },
    'B': {
        '': None
        'A': {
            'B': {
                '': None
            }
        }
    }
}

同样 BABA 会变成：

{
    'A': {
        '': None
        'B': {
            'A': {
                '': None
            }
        }
    },
    'B': {
        'A': {
            '': None,
            'B': {
                'A': {
                    '': None
                }
            }
        }
    }
}

对于看起来像这样的数据结构，天真 Python 比较它们看起来像：

def tree_intersection_depth (trees):
    best_depth = 0
    for (char, deeper) in trees[0].items():
        if deeper is None:
            continue
        failed = False

        deepers = [deeper]
        for tree in trees[1:]:
            if char in tree:
                deepers.append(tree[char])
            else:
                failed = True
                break

        if failed:
            continue

        depth = 1 + tree_intersection_depth(deepers)
        if best_depth < depth:
            best_depth = depth

    return best_depth

你可以这样称呼它 tree_intersection_depth([tree1, tree2, tree3, ...])。

对于上面的两棵树，它确实给出了 3 作为答案。

现在我真的在写出那个数据结构时作弊了。使后缀树高效的原因是您实际上没有看起来像那样的数据结构。您有一个可以重用所有重复结构的结构。所以模拟设置数据结构并调用它的代码如下所示：

b_ = {'B': {'': None}}
ab_ = {'': None, 'A': b_}
bab_ = {'B': ab_}
abab = {'A': bab_, 'B': ab_}

a_ = {'A': {'': None}}
ba_ = {'': None, 'B': a_}
aba_ = {'A': ba_}
baba = {'B': aba_, 'A': ba_}

print(tree_intersection_depth([abab, baba]))

现在我们可以看到，要获得承诺的性能，还缺少一个步骤。问题是虽然树的大小是 O(n)，但在搜索它时我们可能会访问 O(n^2) 个子字符串。在您的情况下，您不必担心这一点，因为保证子字符串的深度永远不会超过 60。但在完全一般的情况下，您需要添加记忆，以便当递归结果比较数据结构时，您以前看过，您立即 return 旧答案，而不是新答案。（在 Python 中，您将使用 id() 方法将对象的地址与您之前看到的地址进行比较。在 C++ 中，有一组指针元组用于相同的目的。）

求 'n' 个二进制串中最长公共子串的长度

Find the length of the longest common substring in 'n' binary strings

c++

string

algorithm

optimization

longest-substring