c++ - 使用后缀数组实现最长公共(public)子串

Question

我正在使用 this program用于计算后缀数组和最长公共(public)前缀。

我需要计算两个字符串之间的最长公共(public)子串。

为此，我连接字符串 A#B 然后使用 this algorithm .

我有后缀数组 sa[] 和 LCP[] 数组。

最长公共(public)子串是LCP[]数组的最大值。

要找到子串，唯一的条件是在相同长度的子串中，在串B中第一次出现的那个应该是答案。

为此，我保持 LCP[] 的最大值。如果 LCP[curr_index] == max，那么我确保子字符串 B 的 left_index 小于 left_index 的先前值。

但是，这种方法并没有给出正确的答案。错在哪里？

max=-1;
for(int i=1;i<strlen(S)-1;++i)
{
    //checking that sa[i+1] occurs after s[i] or not
    if(lcp[i] >= max && sa[i] < l1 && sa[i+1] >= l1+1 )
    {
        if( max == lcp[i] && sa[i+1] < left_index ) left_index=sa[i+1];

        else if (lcp[i] > ma )
        {
            left_index=sa[i+1];
            max=lcp[i];
        }
    }
    //checking that sa[i+1] occurs after s[i] or not
    else if (lcp[i] >= max && sa[i] >= l1+1 && sa[i+1] < l1 )
    {
        if( max == lcp[i] && sa[i] < left_index) left_index=sa[i];

        else if (lcp[i]>ma)
        {
            left_index=sa[i];
            max=lcp[i];
        }
    }
}

Answer 1

AFAIK，这个问题来自一个编程竞赛，在社论发布之前讨论正在进行的竞赛的编程问题不应该......虽然我在得到错误答案 后缀数组。然后我使用了 suffix Automaton 这让我接受了。

后缀数组适用于 O(nlog^2 n)而后缀自动机在 O(n) 中工作.所以我的建议是使用后缀 Automaton，你一定会被接受。如果你能编码solution for that problem ，您一定会编写此代码。

还在 codchef 论坛中发现:

Try this case 
babaazzzzyy 
badyybac 
The suffix array will contain baa... (From 1st string ) , baba.. ( from first string ) , bac ( from second string ) , bad from second string .
So if you are examining consecutive entries of SA then you will find a match at "baba" and "bac" and find the index of "ba" as 7 in second string , even though its actually at index 1 also . 
Its likely that you may output "yy" instead of "ba"

并且还处理约束 ...在第二个字符串上找到的第一个最长的公共(public)子字符串，应该写入输出... 将非常容易在后缀自动机的情况下。祝你好运!