c - 搜索两个字符串中最长的子串

Question

任务是这样的:找到在两行中找到的最长子串。问题的特殊性在于这些行很长(文件的内容，即每行 400,000 个字符)，而它们由短的字母组成 - 4 个字符。

字符串可以有不同的长度。

我发明并实现了以下算法:

1. 获取第一个文件的内容并写入字符串str1，去掉换行符

2. 获取第二个文件的内容并写入字符串str2，去掉换行符

3. 我们将考虑字符串 str1 的所有子字符串，从最长到最短。为此，在每次迭代时定义循环 while (i>0)，在主要内容之后将字符串的长度减一。长度为 1 的字符串也是如此。

4. while 循环内部:所有长度为 N 的子串仅在开始位置不同。

设一个长度为N的字符串:

• 它是一个长度为N的子串，包含，从位置0开始。

• 有两个长度为N-1的子串从位置0和1开始

• 其中三个长度为 N-2 的子串，从位置 0、1 和 2 开始

...

• K+1个长度为N-K的子串，从位置0,1,...,K开始

for循环中计数的起始位置(z=0; z<=g-i; z++)，其中函数调用getSubstring接收子串。然后使用字符串 str2 的子字符串运行标准函数 strstr

但是这个算法够长吗。有没有办法让它更快？

P.S.用C写

Answer 1

至少有两个经典选项可以有效地求解最长公共(public)子串

• 构建一个通用的 suffix array或两个字符串的后缀树。可以看出，LCS是后缀数组中相邻两个不同颜色(属于不同字符串)的后缀的前缀。我 once wrote an answer描述了一个简单的 O(n log n) 后缀数组构造算法
• 构建一个字符串的后缀自动机，并将另一个字符串输入其中。在每一点检查你在自动机中的“深度”，并报告所有这些深度的最大值。你可以find a C++ implementation在我的 GitHub 上。