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

题意

题目链接

Sol

这题打死我也不会想到后缀数组的,应该会全程想AC自动机之类的吧

但知道这题能用后缀数组做之后应该就不是那么难了

首先把\(S\)和\(S0\)拼到一起跑,求出Height数组

暴力枚举每个后缀是否能成为答案。

具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

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 条评论
登录 后参与评论

相关文章

来自专栏包子铺里聊IT

那些年我们一起遍历过的树

这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这...

2697
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

1622
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

6006
来自专栏数据结构与算法

洛谷P2870 [USACO07DEC]最佳牛线,黄金Best Cow Line, Gold

题目描述 FJ is about to take his N (1 ≤ N ≤ 30,000) cows to the annual"Farmer of the...

2805
来自专栏ml

HDUOJ-------1753大明A+B(大数之小数加法)

大明A+B Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

35912
来自专栏Golang语言社区

实效go编程--2

Go函数的返回值或结果“形参”可被命名,并作为常规变量使用,就像传入的形参一样。 命名后,一旦该函数开始执行,它们就会被初始化为与其类型相应的零值; 若该函数执...

3477
来自专栏Python攻城狮

Python数据科学(七)- 资料清理(Ⅱ)1.资料转换2.处理时间格式资料3.重塑资料4.学习正则表达式5.实例处理

注意:这里的时间转换后的格式可以根据需要设定,eg:dt.strftime('%Y/%m/%d')

1193
来自专栏数据之美

Python Tips, Tricks, and Hacks

一、快速技巧 1.1、4 种引号 '  '''  "  """  print """I wish that I'd never heard him say...

2735
来自专栏GreenLeaves

C# String.Format的格式限定符与Format方法将多个对象格式化一个字符串原理

Format方法将多个对象格式化成一个字符串Format方法解析格式字符串的原理:

1242
来自专栏数据结构与算法

3027 线段覆盖 2

3027 线段覆盖 2  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descript...

2956

扫码关注云+社区

领取腾讯云代金券