2018-01-25

最长重复子串-LRS

此问题是针对单个字符里面出现的子串的重复的最长的长度称为最长重复子串(Longest Repeat Substring)LRS

针对子串是否重叠，又可以分为可重叠的最长重复子串 和 不可重叠的重复子串。

可重叠的最长重复子串参考后缀数组求最长重复子串
有关更多后缀数组的题参考 vjudge->后缀数组入门

基本思路：

通过后缀数组找到所有的子串
排序得到前后关联比较大的子串序列。注意排序完成后 对于一个子串，一个与其重复最多的字符串肯定是紧挨着自己的两个字符串
遍历每个子串，将其与前后两个子串相比较，得到两者相同长度较大的一者
遍历所有得到的相同的长度，取最大的就是最长的公共子串

示例

例如： banana 可以重复的最长子串是 ana
示例代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getCommonLnegth(string &self, string &compare)
{
    const int len = min(self.length(),compare.length());
    for(int j = 0; j < len; ++j)
    {
        if(self[j] != compare[j])
            return j;
    }
}

int main(int argc, char *argv[])
{
    string words = "banana";
    vector<string > suffix;
    const int len = words.length();
    //int count = len;
    for(int i = 0; i < len; ++i)
    {
        suffix.push_back(words.substr(i,len-i));
    }

    // 对后缀数组进行排序
    // 注意到 排序完成之后 每个子序列的最长重复的另一子序列要么在其前面，要么在其后面
    sort(suffix.begin(),suffix.end());

    vector<int > commonLen(len,0);

    // 得到每个子序列的最长重复长度
    for(int i = 0; i < len; ++i)
    {
        if(i != 0 && i != len -1)
        {
             commonLen[i] = max(getCommonLnegth(suffix[i],suffix[i-1]),getCommonLnegth(suffix[i],suffix[i+1]));
        }
        else if(i == 0)
        {
            commonLen[i] = getCommonLnegth(suffix[i],suffix[i+1]);
        }
        else if(i == len -1)
        {
            commonLen[i] = getCommonLnegth(suffix[i],suffix[i-1]);
        }
    }

    int index = 0,maxLen = 0;
    for(int i = 0; i < len; ++i)
    {
        if(maxLen < commonLen[i])
        {
            index = i;
            maxLen = commonLen[i];
        }
    }
    for(int i = 0; i < maxLen; ++i)
    {
        cout<<suffix[index][i];
    }
    cout<<endl;
    return 0;
}

不可重叠最长重复子串
顾名思义，前后的子串是在不能重叠的情况下面的最长的重复的长度

此问题是针对单个字符里面出现的子串的重复的最长的长度 称为最长重复子串(Longest Repeat Substring)LRS

基本思路：

示例

类似题型变种还有:

此问题是针对单个字符里面出现的子串的重复的最长的长度称为最长重复子串(Longest Repeat Substring)LRS