bzoj4556

后缀自动机+二分+倍增+线段树合并

后缀自动机真好用

后面一个串是固定的，那么我们要对前面的串进行一些操作。我们想既然是求lcp，那么我们得先翻转原串，这样前缀变成了后缀，然后二分一下，从d在自动机上的位置向上倍增，走到第一个Max大于当前答案的位置，用线段树合并判断一下当前是否满足。还是很好写的，具体看代码。注意线段树合并必须新开一个节点。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;
int fa[N][19], mp[N << 1];
vector<int> G[N];
namespace Segment_Tree
{
    int cnt;
    int root[N], sum[N * 25], lc[N * 25], rc[N * 25];
    void update(int &x, int l, int r, int p, int d)
    {
        x = ++cnt;
        sum[x] += d;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(p <= mid) update(lc[x], l, mid, p, d);
        else update(rc[x], mid + 1, r, p, d);
    }
    int merge(int u, int v)
    {
        if(!u) return v;
        if(!v) return u;
        int w = ++cnt;
        sum[w] = sum[u] + sum[v];
        lc[w] = merge(lc[u], lc[v]);
        rc[w] = merge(rc[u], rc[v]);
        return w;
    }
    int query(int x, int l, int r, int a, int b)
    {
        if(!x || l > b || r < a) return 0;
        if(l >= a && r <= b) return sum[x];
        int mid = (l + r) >> 1;
        return (query(lc[x], l, mid, a, b) + query(rc[x], mid + 1, r, a, b)); 
    }
} using namespace Segment_Tree;
namespace SAM 
{
    struct node {
        int val, par;
        int ch[26];
    } t[N];
    int sz = 1, Root = 1, last = 1;
    int nw(int x)
    {
        t[++sz].val = x;
        return sz;
    }
    void extend(int c)
    {
        int p = last, np = nw(t[p].val + 1);
        while(p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].par;
        if(!p) t[np].par = Root;
        else
        {
            int q = t[p].ch[c];
            if(t[q].val == t[p].val + 1) t[np].par = q;
            else
            {
                int nq = nw(t[p].val + 1);
                memcpy(t[nq].ch, t[q].ch, sizeof(t[q].ch));
                t[nq].par = t[q].par;
                t[q].par = t[np].par = nq;
                while(p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].par;
            }
        }
        last = np;
        mp[t[np].val] = np;
        update(root[np], 1, n, t[np].val, 1);
    }
    void dfs(int u)
    {
        for(int i = 0; i < G[u].size(); ++i) 
        {
            int v = G[u][i];
            fa[v][0] = u;
            dfs(v);
            root[u] = merge(root[u], root[v]);
        }
    }
} using namespace SAM;
char s[N];
bool check(int len, int l, int r, int u)
{   
    for(int i = 18; i >= 0; --i) 
        if(t[fa[u][i]].val >= len) 
            u = fa[u][i];
//  if(t[u].val < len) return 0;
    return query(root[u], 1, n, l + len - 1, r);
}
int main()
{
//  freopen("heoi2016_str.in", "r", stdin);
//  freopen("heoi2016_str.out", "w", stdout);
    scanf("%d%d%s", &n, &m, s + 1);
    reverse(s + 1, s + n + 1);
    for(int i = 1; i <= n; ++i) extend(s[i] - 'a');
    for(int i = 2; i <= sz; ++i) G[t[i].par].push_back(i);
    dfs(Root); 
    for(int j = 1; j <= 18; ++j)
        for(int i = 1; i <= sz; ++i) 
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    while(m--)
    {
        int a, b, c, d, ta, tb, tc, td;
        scanf("%d%d%d%d", &ta, &tb, &tc, &td);
        a = n - tb + 1;
        b = n - ta + 1;
        c = n - td + 1;
        d = n - tc + 1;
        int l = 0, r = min(b - a + 2, d - c + 2), ans = 0;
        while(r - l > 1)
        {
            int mid = (l + r) >> 1;
            if(check(mid, a, b, mp[d])) l = ans = mid;
            else r = mid;
        }
        printf("%d
", ans);
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}