【luoguP4094】[HEOI2016/TJOI2016]字符串

学艺不精学艺不精,sa&sam都是一瓶子不满半瓶子咣当,自闭了。
现在我们要求公共前缀,对sam来说,前缀不好求但后缀好求,翻转整个串,这样就变成公共后缀了,并且这个后缀满足,对于s[b-len+1,a],存在一个结束点和s[d,c]在同一个endpos集合里面并且长度长度至少为len。那么就倒序建一个sam,然后模拟建出后缀树(常见套路),并用线段树合并来维护endpos。
询问的时候二分答案,并且从c所在位置沿着后缀树往上面跳,跳到长度不小于二分值的最上方。然后线段树查询即可。
看不透sa的解法,突然发现自己不懂为什么height维护的是sa_i却可以做原串的lcp,自闭。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef unsigned int uint;

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 1e5 + 10; 

int n, m, tmpsz[ms << 1], poi[ms << 1], pos[ms];

char s[ms];

struct Sam
{
    int ch[ms << 1][26], len[ms << 1], cnt, las, Root[ms << 1], fa[ms << 1][21];

    struct Seg
    {
        int ch[ms << 6][2], su[ms << 6], tot;

        void insert(int &w, int l, int r, int ll)
        {
            if(!w)
                w = ++ tot;
            if(l == r)
            {
                su[w] ++; return;
            }
            int mid = (l + r) >> 1;
            if(ll <= mid)
                insert(ch[w][0], l, mid, ll);
            else
                insert(ch[w][1], mid + 1, r, ll);
            su[w] = su[ch[w][0]] + su[ch[w][1]];
        }

        int merge(int x, int y, int l, int r)
        {
            if((!x) || (!y))
                return x + y;
            if(l == r)
            {
                su[x] += su[y]; return x;
            }
            int mid = (l + r) >> 1, rt = ++ tot;
            ch[rt][0] = merge(ch[x][0], ch[y][0], l, mid), ch[rt][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
            su[rt] = su[ch[rt][0]] + su[ch[rt][1]];
            return rt;
        }

        int ask(int w, int l, int r, int ll, int rr)
        {
            if(!w)
                return 0;
            if(l == ll && r == rr)
                return su[w];
            int mid = (l + r) >> 1;
            if(rr <= mid)
                return ask(ch[w][0], l, mid, ll, rr);
            else if(ll > mid)
                return ask(ch[w][1], mid + 1, r, ll, rr);
            return ask(ch[w][0], l, mid, ll, mid) + ask(ch[w][1], mid + 1, r, mid + 1, rr);
        }
    }seg;

    inline void insert(int c)
    {
        int p = ++ cnt; len[p] = len[las] + 1;
        while(las && (!ch[las][c]))
            ch[las][c] = p, las = fa[las][0];
        if(!las)
            fa[p][0] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p][0] = x;
            else
            {
                int q = ++ cnt; len[q] = len[las] + 1, fa[q][0] = fa[x][0];
                memcpy(ch[q], ch[x], sizeof(ch[q])), fa[x][0] = q, fa[p][0] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las][0];
            }
        }
        las = p;
    }

    inline void build()
    {
        cnt = 1, las = 1;
        reverse(s + 1, s + 1 + n);
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a'), seg.insert(Root[las], 1, n, i), pos[i] = las;
        for(ri i = 1; i <= cnt; i ++)
            tmpsz[len[i]] ++;
        for(ri i = 1; i <= n; i ++)
            tmpsz[i] += tmpsz[i - 1];
        for(ri i = 1; i <= cnt; i ++)
            poi[tmpsz[len[i]] --] = i;
        for(ri i = 1; i <= 20; i ++)
            for(ri j = 1; j <= cnt; j ++)
                fa[j][i] = fa[fa[j][i - 1]][i - 1];
        for(ri i = cnt; i; i --)
            if(fa[poi[i]][0])
                Root[fa[poi[i]][0]] = seg.merge(Root[fa[poi[i]][0]], Root[poi[i]], 1, n);
    }

    inline bool check(int Len, int p, int l, int r)
    {
        for(ri i = 20; ~i; i --)
            if(len[fa[p][i]] >= Len && fa[p][i])
                p = fa[p][i];
        //cout << p << '\n';
        return seg.ask(Root[p], 1, n, l + Len - 1, r);
    }

    inline void solve()
    {
        int a, b, c, d;
        while(m --)
        {
            re(a), re(b), re(c), re(d);
            a = n + 1 - a, b = n + 1 - b, c = n + 1 - c, d = n + 1 - d;
            int l = 0, r = min(a - b + 1, c - d + 1), ans = 0;
            while(l <= r)
            {
                int mid = (l + r) >> 1;
                if(check(mid, pos[c], b, a))
                    ans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }   
            printf("%d\n", ans);
        }
    }
}sam;

int main()
{
    re(n), re(m);
    scanf("%s", s + 1);
    sam.build(), sam.solve();
}