正文

BZOJ 3230: 相似子串( RMQ + 后缀数组 + 二分 )

IP云
IP云V管理员/3 阅读
09/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

二分查找求出k大串, 然后正反做后缀数组, RMQ求LCP, 时间复杂度O(NlogN+logN)

---------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
 
using namespace std;
 
typedef long long ll;
 
const int maxlog = 20;
const int maxn = 100009;
 
int N, Q;
 
inline int readint() {
char c = getchar();
for(; !isdigit(c); c = getchar());
int ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
 
inline ll readll() {
char c = getchar();
for(; !isdigit(c); c = getchar());
ll ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
 
struct SA {
int Sa[maxn], Rank[maxn], Height[maxn], cnt[maxn], RMQ[maxlog][maxn];
ll Sm[maxn];
char S[maxn];
#define Cmp(a, b) ((y[a] == y[b]) && (y[a + k] == y[b + k]))
#define b(i) (1 << (i))
void Build() {
int m = 'z' + 1, *x = Rank, *y = Height;
for(int i = 0; i < m; i++) cnt[i] = 0;
for(int i = 0; i < N; i++) cnt[x[i] = S[i]]++;
for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(int i = N; i--; ) Sa[--cnt[x[i]]] = i;
for(int k = 1, p = 0; k <= N; k <<= 1, p = 0) {
for(int i = N - k; i < N; i++) y[p++] = i;
for(int i = 0; i < N; i++)
if(Sa[i] >= k) y[p++] = Sa[i] - k;
for(int i = 0; i < m; i++) cnt[i] = 0;
for(int i = 0; i < N; i++) cnt[x[y[i]]]++;
for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(int i = N; i--; ) Sa[--cnt[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[Sa[0]] = 0;
for(int i = 1; i < N; i++)
x[Sa[i]] = Cmp(Sa[i], Sa[i - 1]) ? p - 1 : p++;
if(p >= N) break;
m = p;
}
for(int i = 0; i < N; i++) Rank[Sa[i]] = i;
Height[0] = 0;
for(int i = 0, h = 0; i < N; i++) if(Rank[i]) {
if(h) h--;
while(S[i + h] == S[Sa[Rank[i] - 1] + h]) h++;
Height[Rank[i]] = h;
}
}
void Query_Init() {
Sm[0] = N - Sa[0] - 1;
for(int i = 1; i < N; i++) Sm[i] = Sm[i - 1] + N - Sa[i] - Height[i] - 1;
for(int i = 0; i < N; i++) RMQ[0][i] = Height[i];
for(int i = 1; b(i) <= N; i++)
for(int j = 0; j + b(i) <= N; j++)
RMQ[i][j] = min(RMQ[i - 1][j], RMQ[i - 1][j + b(i - 1)]);
}
int LCP(int x, int y) {
x = Rank[x], y = Rank[y];
if(x == y) return N;
if(x > y) swap(x, y);
x++;
int Log = 0;
while(b(Log) <= y - x + 1) Log++;
Log--;
return min(RMQ[Log][x], RMQ[Log][y - b(Log) + 1]);
}
pair<int, int> Get(ll v) {
int p = lower_bound(Sm, Sm + N, v) - Sm;
if(p >= N) return make_pair(-1, -1);
if(p) v -= Sm[p - 1];
return make_pair(Sa[p], Sa[p] + v + Height[p] - 1);
}
} A, B;
 
void Init() {
N = readint(), Q = readint();
char c = getchar();
for(; !islower(c); c = getchar());
A.S[0] = B.S[N - 1] = c;
for(int i = 1; i < N; i++)
A.S[i] = B.S[N - i - 1] = getchar();
A.S[N] = B.S[N] = '$';
N++;
}
 
#define L(x) x.first
#define R(x) x.second
 
void Work() {
A.Build(), A.Query_Init();
B.Build(), B.Query_Init();
ll l, r;
while(Q--) {
l = readll(), r = readll();
pair<int, int> L = A.Get(l), R = A.Get(r);
if(L(L) == -1 || L(R) == -1) {
puts("-1");
} else {
int mn = min(R(L) - L(L) + 1, R(R) - L(R) + 1);
int a = min(A.LCP(L(L), L(R)), mn);
int b = min(B.LCP(N - R(L) - 2, N - R(R) - 2), mn);
printf("%lld\n", ll(a) * a + ll(b) * b);
}
}
}
 
int main() {
Init();
Work();
return 0;
}

---------------------------------------------------------------------

3230: 相似子串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1186  Solved: 282
[Submit][Status][Discuss]

Description

Input

输入第1行，包含3个整数N，Q。Q代表询问组数。
第2行是字符串S。
接下来Q行，每行两个整数i和j。（1≤i≤j）。

Output

输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。

Sample Input

5 3
ababa
3 5
5 9
8 10

Sample Output

18
16
-1

HINT

样例解释

第1组询问：两个子串是“aba”,“ababa”。f = 32 + 32 = 18。

第2组询问：两个子串是“ababa”,“baba”。f = 02 + 42 = 16。

第3组询问：不存在第10个子串。输出-1。

数据范围

N≤100000，Q≤100000，字符串只由小写字母'a'~'z'组成

Source

后缀数组+二分+RMQ