最长重复子串-LRS

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

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

基本思路:

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

示例

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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;
}

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

类似题型变种还有:

  1. 最长不重叠重复子串 POJ 1743
  2. 可重叠的K次最长重复子串(POJ 3261)
  3. 重复次数最多的连续重复子串的长度(SPOJ 687)
  4. 求重复次数最多的子串 POJ 3693
  5. 至少重复k次的可重叠的最长重复子串 POJ 3882
  6. RMQ (Range Minimum/Maximum Query) 求解中的 ST 算法
  7. LCA 与 RMQ
T B
站点访问量: / , 本页阅读量:
T B