LOJ #2059. 「TJOI / HEOI2016」字符串 二分 SAM

题目链接

题意：给定一个字符串\(s\)，有\(m\)次询问，每次指定两个区间\([a..b]\)和\([c..d]\)，求第一个区间的子串和第二个区间的\(lcp\)的最大值。

考虑二分答案\(mid\)，问题变为判定是否存在以\([a+mid-1..b]\)结尾的长度为\(mid\)的串，与\(s[c..c+mid-1]\)相等。

这里使用后缀自动机

建出\(SAM\)，找到\(c+mid-1\)在后缀自动机对应的节点，倍增找出包含长度\(mid\)的祖先，在它的\(right\)集合里查询是否存在\([a+mid-1..b]\)中的位置。用线段树合并实现

复杂度\(O(n\ log^2\ n)\)

（倍增把小的一维放后面，速度快了\(2\)倍

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
    static bool iosig;
    static char c;
    for (iosig = false, c = read(); !isdigit(c); c = read()) {
        if (c == '-') iosig = true;
        if (c == -1) return;
    }
    for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
    if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
    if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
    *ooh++ = c;
}
template<class T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) print('0');
    else {
        if (x < 0) print('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) print((char)buf[cnt--]);
    }
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 100005, M = 19;
int n, m, lim, cnt, cnt2, last, pos[N], b[N], a[N<<1], root[N<<1], fa[N<<1], len[N<<1], lson[N*M*2], rson[N*M*2], f[N<<1][M], ch[N<<1][26];
char str[N];
bool s[N*M*2];
void modify(int l, int r, int &t, int pos){
    s[t?t:t=++cnt2]=1;
    if(l==r) return;
    int mid=l+r>>1;
    if(pos<=mid) modify(l, mid, lson[t], pos); else modify(mid+1, r, rson[t], pos);
}
int Merge(int x, int y){
    if(!x || !y) return x|y;
    int tmp=++cnt2;
    s[tmp]=s[x]||s[y], lson[tmp]=Merge(lson[x], lson[y]), rson[tmp]=Merge(rson[x], rson[y]);
    return tmp;
}
bool query(int l, int r, int t, int L, int R){
    if(!t || L<=l && r<=R) return s[t];
    int mid=l+r>>1;
    if(R<=mid) return query(l, mid, lson[t], L, R);
    else if(L>mid) return query(mid+1, r, rson[t], L, R);
    else return query(l, mid, lson[t], L, R)||query(mid+1, r, rson[t], L, R);
}
inline void extend(int c){
    int p=last, np=++cnt;
    last=cnt, len[np]=len[p]+1;
    while(p && !ch[p][c]) ch[p][c]=np, p=fa[p];
    if(!p) fa[np]=1;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else{
            int nq=++cnt;
            len[nq]=len[p]+1, memcpy(ch[nq], ch[q], sizeof ch[0]);
            fa[nq]=fa[q], fa[q]=fa[np]=nq;
            while(ch[p][c]==q) ch[p][c]=nq, p=fa[p];
        }
    }
    modify(1, n, root[np], len[np]);
    pos[len[np]]=np;
}
inline bool check(int l, int r, int p, int x){
    p=pos[p];
    for(int i=lim; ~i; --i) if(len[f[p][i]]>=x) p=f[p][i];
    return query(1, n, root[p], l, r);
}
int main() {
    read(n), read(m);
    cnt=last=1;
    char tmp;
    while(isspace(tmp=read()));
    extend(tmp-'a');
    for(int i=2; i<=n; ++i) extend(read()-'a');

    for(lim=1; 2<<lim<n; ++lim);
    for(int i=1; i<=cnt; ++i) ++b[len[i]], f[i][0]=fa[i];
    for(int i=1; i<=n; ++i) b[i]+=b[i-1];
    for(int i=cnt; i; --i) a[b[len[i]]--]=i;
    for(int i=cnt; i; --i) root[fa[a[i]]]=Merge(root[fa[a[i]]], root[a[i]]);
    for(int i=1; i<=lim; ++i) for(int j=1; j<=cnt; ++j) f[j][i]=f[f[j][i-1]][i-1];

    while(m--){
        static int a, b, c, d;
        read(a), read(b), read(c), read(d);
        int l=1, r=min(b-a+1, d-c+1), ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(a+mid-1, b, c+mid-1, mid)) ans=mid, l=mid+1; else r=mid-1;
        }
        print(ans), print('\n');
    }
    return flush(), 0;
}

LOJ #2059. 「TJOI / HEOI2016」字符串 二分 SAM

原文：https://www.cnblogs.com/CMXRYNP/p/9606842.html