blob: 4d282a6b5949aea36da239d3c6c4aa776308d07e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
//longest common substring in one string (overlapping not excluded)
//contains suffix array:-------------------------------------------------------------------
string lsubs(string s) {
if(s.length() == 0) return "";
vector<int> a(s.length());
for(int k = 0; k < a.size(); k++) a[k] = k;
sort(a.begin(), a.end(), [&] (const int &u, const int &l) {
int ui = u, li = l;
while(ui < s.length() && li < s.length()) {
if(s[ui] < s[li]) return true;
else if(s[ui] > s[li]) return false;
ui++; li++;
}
return !(ui < s.length());
});
//------------------------------------------------------------------------------------------
int r = 0, m=0, c=0;
for(int i = 0; i < a.size() - 1; i++) {
c = 0;
while(a[i]+c < s.length() && a[i+1]+c < s.length() && s[a[i]+c] == s[a[i+1]+c]) c++;
if(c > m) r=i, m=c;
}
return m == 0 ? "" : s.substr(a[r], m);
}
|
