用后缀数组实现最长的公共子串

Question

我使用这个程序来计算后缀数组和最长的公共前缀。

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

为此，我将字符串( A#B )连接起来，然后使用这种算法。

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

最长的公共子字符串是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，这个问题来自一个编程竞赛，在社论发表之前讨论正在进行的竞赛的编程问题不应该是……虽然我给您一些洞察力，因为我得到了错误的答案，的后缀数组。然后我使用了后缀自动机，这给了我接受。

后缀数组在O(nlog^2 n)中工作，而后缀自动机在O(n)中工作。所以我的建议是用后缀自动机，你肯定会被接受的。如果你能编码这个问题的解决办法，你肯定会对它进行编码。

在厨师长论坛上也发现：

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"

并且也处理约束...the第一个最长的公共子字符串，应该写到输出.在后缀自动机的情况下非常容易。祝你好运！