P4094 [HEOI2016/TJOI2016]字符串

发表于 | 评论数： | 阅读次数：
本文字数： 5.1k | 阅读时长 ≈ 5 分钟

P4094 [HEOI2016/TJOI2016]字符串

传送门

洛谷

题目描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为$n$的字符串s，和$m$个问题。佳媛姐姐必须正确回答这$m$个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有$a,b,c,d$四个参数，问你子串$s[a..b]$的所有子串和$s[c..d]$的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入输出格式

输入格式：

输入的第一行有两个正整数$n,m$，分别表示字符串的长度和询问的个数。接下来一行是一个长为$n$的字符串。接下来$m$行，每行有$4$个数$a,b,c,d$，表示询问$s[a..b]$的所有子串和$s[c..d]$的最长公共前缀的最大值。

输出格式：

对于每一次询问，输出答案。

输入输出样例

输入样例#1：

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

输出样例#1：

1
1
2
2
2

说明

对于$10\%$的数据，$1 \le n,m \le 300$

对于$40\%$的数据，$1 \le n,m \le 3000$,字符串中仅有$a$,$b$

对于$100\%$的数据，$1 \le n,m \le 10^5$,字符串中仅有小写英文字母，$a \le b,c \le d,1 \le a,b,c,d \le n$

分析

我们首先可以看出本题答案是有单调性的。
因为如果一个串可以，那么它的前缀也一定可以，即如果一个答案满足题意，那么所有小于它的答案也都满足题意。
既然有单调性，那么我们可以二分。
我们二分$s[c…d]$的前缀长度为$len$。
那么显然如果满足题意，那么$s[c…c+len-1]$一定是$s[a…b]$的子串。
现在问题就转化成了给你一个串，判断它是不是另一个字符串的子串。
似乎很多人都是用$SA$做的，可是本蒟蒻不会$SA$…
所以我们想想$SAM$的做法。
其实很好想如果它是子串，那么它一定在另一个串的$Endpos$中。
我们就只需要判断是不是这个串的$Endpos$中有$a+len-1…b$中任何一个数出现。
这个显然权值线段树可以搞定。
那么我们怎么求$Endpos$集合？
线段树合并就行了。
还有一个小细节就是，不是直接在子串在$SAM$上的节点的线段树里找，而是一直往上跳祖先，直到这个节点的$len_i$是满足$len_i \ge len$的最小值。因为长度越小$Endpos$的元素越多，找到的概率就越大（说人话就是不会漏解）。
另外，我不知道用$SAM$为什么一定要把串翻过来，不翻也照样做啊？

吐槽：Owen_codeisking题解中的$SAM$解法阵亡了，弄得我对拍的时候一直以为我打错了，浪费了好多时间。
hack数据：
4 1
mktk
3 4 1 4
正确输出：
1

参考资料

mrclr的 [HEOI2016/TJOI2016]字符串
Owen_codeisking的 [HEOI2016/TJOI2016]字符串（后缀数组+二分+主席树/后缀自动机+倍增+线段树合并）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
struct Node
{
    int l,r;
    int val;
}node[maxn*60];
int n,m,a,b,c,d,tot,cnt=1,las=1,T[maxn<<1],pac[maxn],ns[maxn<<1];
int len[maxn<<1],fa[maxn<<1][21],ch[maxn<<1][26],ton[maxn<<1];
void insert(int &k,int l,int r,int x)
{
    if(!k)k=++tot;
    if(l==r)
    {
        node[k].val+=1;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)insert(node[k].l,l,mid,x);
    else insert(node[k].r,mid+1,r,x);
    node[k].val=node[node[k].l].val+node[node[k].r].val;
}
int merge(int x,int y,int l,int r)
{
    if(!x||!y)return x+y;
    if(l==r)
    {
        node[x].val+=node[y].val;
        return x;
    }
    int mid=(l+r)>>1,z=++tot;
    node[z].l=merge(node[x].l,node[y].l,l,mid);
    node[z].r=merge(node[x].r,node[y].r,mid+1,r);
    node[z].val=node[node[z].l].val+node[node[z].r].val;
    return z;
}
int query(int k,int l,int r,int x,int y)
{
    if(!k)return 0;
    if(l>=x&&r<=y)return node[k].val;
    int mid=(l+r)>>1;
    if(y<=mid)return query(node[k].l,l,mid,x,y);
    if(x>mid)return query(node[k].r,mid+1,r,x,y);
    return query(node[k].l,l,mid,x,y)+query(node[k].r,mid+1,r,x,y);
}
void insert(int cc,int i)
{
    int p=las,np=las=++cnt;
    len[np]=len[p]+1;
    pac[i]=np;
    for(;p&&!ch[p][cc];p=fa[p][0])ch[p][cc]=np;
    if(!p)fa[np][0]=1;
    else
    {
        int q=ch[p][cc];
        if(len[q]==len[p]+1)fa[np][0]=q;
        else
        {
            int nq=++cnt;
            len[nq]=len[p]+1;
            fa[nq][0]=fa[q][0];
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[q][0]=fa[np][0]=nq;
            for(;p&&ch[p][cc]==q;p=fa[p][0])ch[p][cc]=nq;
        }
    }
}
bool check(int mid)
{
    if(!mid)return true;
    int now=pac[c+mid-1];
    for(int i=20;i>=0;i--)
        if(fa[now][i]&&len[fa[now][i]]>=mid)
            now=fa[now][i];
    return query(T[now],1,n,a+mid-1,b);
}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        insert(getchar()-'a',i);
        insert(T[pac[i]],1,n,i);
    }
    for(int i=1;i<=cnt;i++)ton[len[i]]+=1;
    for(int i=1;i<=cnt;i++)ton[i]+=ton[i-1];
    for(int i=1;i<=cnt;i++)ns[ton[len[i]]--]=i;
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<21;j++)
            fa[ns[i]][j]=fa[fa[ns[i]][j-1]][j-1];
    for(int i=cnt;i>=1;i--)
        T[fa[ns[i]][0]]=merge(T[fa[ns[i]][0]],T[ns[i]],1,n);
    for(int i=1;i<=m;i++)
    {
        read(a,b,c,d);
        int l=0,r=min(b-a+1,d-c+1);
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid))l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",r);
    }
    return 0;
}