LibreOJ 3298 「BJOI2020」封印

明明是唯一一道区分题能不能认真点啊喂（
怎么出得这么 naive 啊（

首先用任何一种后缀数据结构对 1≤i≤|S| 求出 li=max{j∣Si−j+1…i∈substrings(T)}

那么容易发现答案即是 max{min(li,i−l+1)∣l≤i≤r}。
讨论一下 i−li+1 的大小，容易发现其有单调性，可以二分然后 RMQ。
线性的话离线双指针然后 O(1) RMQ 即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5;
const int LG = 20;
int n,m,q,lg2[N + 5];
char s[N + 5],t[N + 5];
int len[N + 5];
int st[LG + 5][N + 5];
inline int query(int l,int r)
{
    int lg = lg2[r - l + 1];
    return max(st[lg][l],st[lg][r - (1 << lg) + 1]);
}
int ans;
namespace SAM
{
    struct node
    {
        int ch[2];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
    {
        for(register int i = 1;i <= m;++i)
            insert(t[i] - 'a');
        for(register int i = 1,x,p = 1,l = 0;i <= n;++i)
        {
            x = s[i] - 'a';
            if(sam[p].ch[x])
                p = sam[p].ch[x],++l;
            else
            {
                for(;p && !sam[p].ch[x];p = sam[p].fa);
                !p ? (p = 1,l = 0) : (l = sam[p].len + 1,p = sam[p].ch[x]);
            }
            st[0][i] = len[i] = l;
        }
    }
}
inline int get(int L,int R)
{
    int l = L,r = R,mid,ret = R + 1;
    while(l <= r)
        mid = l + r >> 1,mid - len[mid] + 1 >= L ? (r = mid - 1,ret = mid) : (l = mid + 1);
    return ret;
}
int main()
{
    scanf("%s%s%d",s + 1,t + 1,&q),n = strlen(s + 1),m = strlen(t + 1);
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i >> 1] + 1;
    SAM::build();
    for(register int i = 1;(1 << i) <= n;++i)
        for(register int j = 1;j + (1 << i) - 1 <= n;++j)
            st[i][j] = max(st[i - 1][j],st[i - 1][j + (1 << i - 1)]);
    for(int l,r,x;q;--q)
    {
        scanf("%d%d",&l,&r),x = get(l,r),ans = 0;
        x > l && (ans = max(ans,x - l));
        x <= r && (ans = max(ans,query(x,r)));
        printf("%d\n",ans);
    }
}