# 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

## Sol

rmq维护一下区间lcp最小值

BZOJ上被完美卡常

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 2333;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, L, rak[MAXN], tax[MAXN], tp[MAXN], sa[MAXN], H[MAXN], f[MAXN][20], lg2[MAXN];
char s[MAXN], s0[MAXN];
void Qsort() {
for(int i = 0; i <= M; i++) tax[i] = 0;
for(int i = 1; i <= N; i++) tax[rak[i]]++;
for(int i = 1; i <= M; i++) tax[i] += tax[i - 1];
for(int i = N; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
void SuffixSort() {
for(int i = 1; i <= N; i++) rak[i] = s[i], tp[i] = i; M = 233; Qsort();
for(int w = 1, p = 0; p < N; w <<= 1, M = p) { p = 0;
for(int i = 1; i <= w; i++) tp[++p] = N - i + 1;
for(int i = 1; i <= N; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
Qsort(); swap(tp, rak); rak[sa[1]] = p = 1;
for(int i = 2; i <= N; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;
}
for(int i = 1, k = 0; i <= N; i++) {
if(k) k--; int j = sa[rak[i] - 1];
while(s[i + k] == s[j + k]) k++;
H[rak[i]] = k;
}
}
void Pre() {
for(int i = 1; i <= N; i++) f[i][0] = H[i];
for(int j = 1; j <= 17; j++)
for(int i = 1; i + (1 << j) - 1 <= N; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int Query(int x, int y) {
if(x > y) swap(x, y); x++;
int k = lg2[y - x + 1];
return min(f[x][k], f[y - (1 << k) + 1][k]);
}
int check(int x, int y, int dep) {
if(dep == 3) return Query(rak[x], rak[y]);
int num = Query(rak[x], rak[y]);
num +=  check(x + num + 1, y + num + 1, dep + 1) + 1;
return num;
}
void solve() {
scanf("%s%s", s + 1, s0 + 1);
L = strlen(s0 + 1); N = strlen(s + 1);
for(int i = 1; i <= L; i++) s[N + i] = s0[i];
N += L;
SuffixSort(); Pre(); N -= L; int ans = 0;
for(int i = 1; i <= N - L + 1; i++) if(check(i, N + 1, 0) >= L) ans++;
printf("%d\n", ans);
}
int main() {
//freopen("a.in", "r", stdin);
lg2[1] = 0; for(int i = 2; i <= MAXN - 1; i++) lg2[i] = lg2[i >> 1] + 1;
for(int T = read(); T; solve(), T--);
return 0;
}
/*
2
ATCGCCCTA
CTTCA
ATCGCCCTA
CTTCA
*/

0 条评论

• ### P1197 [JSOI2008]星球大战

题目描述 很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几...

• ### 04:垂直直方图

4:垂直直方图 总时间限制: 1000ms 内存限制: 65536kB描述 输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注...

• ### 10:Challenge 3（树状数组直接修改）

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列，有M次操作，每次操作是以下两种之一： （1）...

• ### 数组的简单练习题

1.将一个给定的整型数组转置输出， 例如： 源数组，1 2 3 4 5 6 转置之后的数组，6 5 4 3 2 1

• ### 【CodeForces 730H】Car Repair Shop

模拟，先看从s[i]时刻开始修理，和之前i-1个是否冲突。如果冲突，就枚举每个s[j]+d[j]时刻开始，看是否冲突，再从中选择最小的时刻。

• ### P1197 [JSOI2008]星球大战

题目描述 很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几...

• ### 洛谷P4725 【模板】多项式对数函数(多项式ln)

可以直接对两边求导$$G'(A(x)) = F'(A(x))A'(x) = \frac{A(x)}{A'(x)}$$