题目描述
给出一个字符串 S
,考虑其所有重复子串(S
的连续子串,出现两次或多次,可能会有重叠)。
返回任何具有最长可能长度的重复子串。(如果 S
不含重复子串,那么答案为 ""
。)
样例
输入:"banana"
输出:"ana"
输入:"abcd"
输出:""
注意
2 <= S.length <= 10^5
S
由小写英文字母组成。
算法1
(二分 + RK-hash) $O(n \log n)$
- 由于最终重复子串的长度是符合单调性的,所以可以采取二分的方法找到这个长度。
- 每次二分一个长度
len
,我们通过RK-hash
的方法判定长度为len
的重复的子串是否存在。 - 所谓
RK-hash
,是将一个固定长度的字符串看成一个131
进制的数字 (字母'a'
对应 0),我们从开始位置依次取出长度为len
的子串。例如[0, len - 1]
,它的 hash 值就是s[0] * 131 ^ (len - 1) + s[1] * 131 ^ (len - 2) + ... + s[len - 1]
,再模上一个大数。从[0, len - 1]
变到[1, len]
时,需要将上一次的 hash 值减去s[0] * 131 ^ (len - 1)
,然后乘上131
,再加上s[len]
。依此类推,直到[n - len, n - 1]
。 - 由于
RK-hash
不保证无冲突,所以需要通过拉链法来避免冲突。但此题时间限制比较紧,使用uint64
自动溢出不拉链可以过。
时间复杂度
- 二分的时间复杂度为 $O(n \log n)$,每次二分判断的时间复杂度近似为 $O(n)$,所以时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要额外的空间存储哈希值,故空间复杂度为 $O(n)$。
C++ 代码
#define ULL unsigned long long
class Solution {
public:
int check(const string &s, int len, ULL power) {
unordered_set<ULL> seen;
int n = s.length();
ULL hash = 0;
for (int i = 0; i < len; i++)
hash = hash * 131 + s[i] - 'a';
seen.insert(hash);
for (int i = len; i < n; i++) {
hash = hash - power * (s[i - len] - 'a');
hash = hash * 131 + s[i] - 'a';
if (seen.find(hash) != seen.end())
return i - len + 1;
seen.insert(hash);
}
return -1;
}
string longestDupSubstring(string S) {
int n = S.length();
int l = 0, r = n - 1;
vector<ULL> power(n, 1);
for (int i = 1; i < n; i++)
power[i] = power[i - 1] * 131;
while (l < r) {
int mid = (l + r) >> 1;
if (check(S, mid + 1, power[mid]) == -1) {
r = mid;
} else {
l = mid + 1;
}
}
if (l == 0)
return "";
return S.substr(check(S, l, power[l - 1]), l);
}
};
算法2
(后缀自动机/后缀数组) $O(n)$
后缀自动机:
- 对字符串 $S$ 建立后缀自动机,并求每个状态的
end_pos
出现次数并存储第一次出现的位置。 - 对于每个状态,如果其出现的次数大于等于 2,则其本身的
len
值就可以更新答案。
后缀数组:
- 建立后缀数组,求出
height
数组。 height
数组的最大值就是答案。
时间复杂度
- 假设字符集大小为常数,后缀自动机/后缀数组的构造时间为 $O(n)$,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储后缀自动机/后缀数组的所有状态。
C++ 代码
#define N 100010
struct Node {
int len, link, first_pos, cnt;
int nxt[26];
vector<int> inv_link;
Node() {
memset(nxt, -1, sizeof(nxt));
}
};
class Solution {
private:
int sz, last;
Node st[2 * N];
int maxlen, pos;
void init_sam() {
st[0].len = 0;
st[0].link = -1;
sz = 1;
last = 0;
}
void sam_extend(int c) {
int cur = sz++;
st[cur].len = st[last].len + 1;
st[cur].first_pos = st[last].len;
st[cur].cnt = 1;
int p = last;
while (p != -1 && st[p].nxt[c] == -1) {
st[p].nxt[c] = cur;
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].nxt[c];
if (st[q].len == st[p].len + 1) {
st[cur].link = q;
} else {
int clone = sz++;
st[clone].len = st[p].len + 1;
st[clone].link = st[q].link;
st[clone].first_pos = st[q].first_pos;
memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
while (p != -1 && st[p].nxt[c] == q) {
st[p].nxt[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
void dfs(int u) {
for (int v : st[u].inv_link) {
dfs(v);
st[u].cnt += st[v].cnt;
}
if (st[u].cnt >= 2 && maxlen < st[u].len) {
maxlen = st[u].len;
pos = st[u].first_pos - st[u].len + 1;
}
}
public:
string longestDupSubstring(string S) {
init_sam();
for (char c : S)
sam_extend(c - 'a');
for (int i = 1; i < sz; i++)
st[st[i].link].inv_link.push_back(i);
maxlen = 0;
dfs(0);
if (maxlen == 0) return "";
return S.substr(pos, maxlen);
}
};
这份代码过不去了,应该还是要处理hash冲突,
试了一下底取131 hash值改成unsigned longlong, 直接让他溢出取模,另外用拉链法处理冲突,过了,速度还可以
感觉是不是取模操作有点慢
lc 溢出直接报 re 的吧
我这边提交是没有报re的
艹,他只会查 int 的溢出,去掉了取模可以过了。
这道题其实正解应该是后缀数组或者后缀自动机
遗憾,超时了
垃圾 lc,只能按照官方题解模 $2^{32}$ 才能无冲突。只要加上解决冲突必超时。