BZOJ 3230: 相似子串( RMQ + 后缀数组 + 二分 )
2024-08-29 20:30:41
二分查找求出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
ababa
3 5
5 9
8 10
Sample Output
18
16
-1
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
最新文章
- 深入浅出Mybatis系列(三)---配置详解之properties与environments(mybatis源码篇)
- WPF 打印
- 归并排序-java
- 【leetcode】Merge Intervals(hard)
- CSS3盒模型display:box详解
- 【中国剩余定理】POJ 1006 &; HDU 1370 Biorhythms
- 关于CMCC(中国移动)、CU(中国联通)、CT(中国电信)的一些笔记
- [Unity3D]Unity3D游戏开发之《愤慨的小鸟》弹弓实现
- 区间第K大
- ios UIImagePickerController简单说明
- 【算法系列学习】DP和滚动数组 [kuangbin带你飞]专题十二 基础DP1 A - Max Sum Plus Plus
- Hadoop2 和 Hadoop1 区别
- React笔记:快速构建脚手架(1)
- 简单的实现HTTP密码验证登陆
- macs安卓工程创建
- ZBX_NOTSUPPORTED: Cannot obtain filesystem information: [13] Permission denied
- fatal: [db01]: FAILED! =>; {";changed";: false, ";msg";: ";The PyMySQL (Python 2.7 and Python 3.X) or MySQL-python (Python 2.X) module is required.";}
- C++ 关于 CMFCPropertyGridCtrl 的使用方法 之一 (原创)
- echarts实现折线图
- Adventures in deep learning
热门文章
- Linux下装Eclipse C/C++,以及环境配置
- 常用的sql server规范
- ssh框架的搭建
- 关于C语言中有string类型吗?
- Description:一根高筋拉面,中间切一刀,可以得到2根面条。如果先对折1次,中间切一刀,可以得到3根面条。如果连续对折2次,中间切一刀,可以得到5根面条。Input:你的程序需要解决的问题是,输入连续对折的次数。NOutput输出中间切一刀,可以得到多少根面条。
- 解决SVN:could not start external diff program的问题。
- Linux网络管理——Linux网络命令
- 【转】MUD教程--巫师入门教程1
- J2SE知识点摘记-数据库(二)
- Oracle EBS-SQL (BOM-5):检查有BOM但物料状态为NEW的物料.sql