<更新提示>
<第一次更新>
<正文>
[TJOI2016] 字符串
Description
佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？
Input Format
输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。
Output Format
对于每一次询问，输出答案。
Sample Input
5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4
Sample Output
1
1
2
2
2
解析
看到最长公共前缀，先建立后缀树，只需把字符串倒序插入后缀自动机即可。
容易知道$s[c,d]$在后缀树上对应一个从根节点竖直向下的链，$lcp$也是，那么我们可以先找到后缀$c$对应的叶节点。容易得知答案具有单调性，那么我们可以先二分一下答案，然后从刚才找到的$c$点对应的叶节点开始向上倍增定位到答案长度对应的点。这样就可以找到答案在后缀树上对应的点了，设其为$p$。
$p$符合要求，当且仅当$mathrm(p)$是$s[a,b]$的一个子串。考虑到一个字符串的子串一定可以表示为其一个后缀的前缀，那么我们只需要查询节点$p$在后缀树的子树中是否有这些后缀$[a,b-mid+1](对应的叶节点就可以了。如果有，那么说明)mathrm(p)$是这些后缀的一个前缀，并且长度为$mid$，所以他就是$s[a,b]$的一个子串，符合要求。
那么子树查询后缀位置的并可以用可持久化线段树合并轻松的实现。
(Code:)
#include <bits/stdc++.h>
using namespace std;
const int N = 200020 , Maxlog = 25;
struct Node { int ls,rs; };
struct SegmentTree
{
Node ver[N*Maxlog]; int tot;
#define ls(p) ver[p].ls
#define rs(p) ver[p].rs
#define mid ( l + r >> 1 )
SegmentTree () { tot = 0; }
inline void Insert(int &p,int l,int r,int v)
{
if (!p) p = ++tot; if ( l == r ) return void();
if ( v <= mid ) Insert( ls(p) , l , mid , v );
if ( v > mid ) Insert( rs(p) , mid+1 , r , v );
}
inline int Merge(int p,int q)
{
if ( !p || !q ) return p|q;
int cur = ++tot;
ls(cur) = Merge( ls(p) , ls(q) );
rs(cur) = Merge( rs(p) , rs(q) );
return cur;
}
inline bool Query(int p,int l,int r,int ql,int qr)
{
if ( !p || ql > qr ) return false; int res = false;
if ( ql <= l && r <= qr ) return true;
if ( ql <= mid ) res |= Query( ls(p) , l , mid , ql , qr );
if ( qr > mid ) res |= Query( rs(p) , mid+1 , r , ql , qr );
return res;
}
#undef mid
};
struct SuffixAutomaton
{
int trans[N][26],link[N],maxlen[N],buc[N],ord[N],tot,last;
int n,rec[N],id[N],anc[N][Maxlog],root[N]; SegmentTree P;
SuffixAutomaton () { tot = last = 1; }
inline void Extend(int c,int pos)
{
int cur = ++tot , p = last;
maxlen[cur] = maxlen[last] + 1;
rec[pos] = cur , id[cur] = pos;
while ( p && !trans[p][c] )
trans[p][c] = cur , p = link[p];
if ( p == 0 ) link[cur] = 1;
else {
int q = trans[p][c];
if ( maxlen[q] == maxlen[p] + 1 ) link[cur] = q;
else {
int cl = ++tot; maxlen[cl] = maxlen[p] + 1;
memcpy( trans[cl] , trans[q] , sizeof trans[q] );
while ( p && trans[p][c] == q )
trans[p][c] = cl , p = link[p];
link[cl] = link[q] , link[q] = link[cur] = cl;
}
}
last = cur;
}
inline void Topsort(void)
{
for (int i = 1; i <= tot; i++) ++buc[ maxlen[i] ];
for (int i = 1; i <= n; i++) buc[i] += buc[i-1];
for (int i = 1; i <= tot; i++) ord[ buc[maxlen[i]]-- ] = i;
}
inline void Rebuild(char *s)
{
n = strlen( s+1 );
for (int i = n; i >= 1; i--)
Extend( s[i]-'a' , i ) , P.Insert( root[last] , 1 , n , i );
Topsort();
for (int i = tot; i >= 2; i--)
{
int u = ord[i] , Fa = link[u];
anc[u][0] = Fa , root[Fa] = P.Merge( root[Fa] , root[u] );
}
anc[1][0] = -1;
for (int i = 1; i <= tot; i++)
for (int k = 1; k < Maxlog; k++)
if ( anc[ord[i]][k-1] == -1 ) anc[ord[i]][k] = -1;
else anc[ord[i]][k] = anc[ anc[ord[i]][k-1] ][k-1];
}
inline bool Check(int Ans,int p,int a,int b)
{
for (int k = Maxlog-1; k >= 0; k--)
if ( anc[p][k] != -1 && maxlen[anc[p][k]] >= Ans )
p = anc[p][k];
return P.Query( root[p] , 1 , n , a , b-Ans+1 );
}
inline int Query(int a,int b,int c,int d)
{
int l = 1 , r = min( b-a+1 , d-c+1 );
while ( l + 1 < r )
{
int mid = l + r >> 1;
Check(mid,rec[c],a,b) ? l = mid : r = mid;
}
return Check(r,rec[c],a,b) ? r : Check(l,rec[c],a,b) ? l : 0;
}
};
SuffixAutomaton T;
int n,m,a,b,c,d; char s[N];
int main(void)
{
scanf( "%d%d" , &n , &m );
scanf( "%s" , s+1 );
T.Rebuild(s);
for (int i = 1; i <= m; i++)
{
scanf( "%d%d%d%d" , &a , &b , &c , &d );
printf( "%d
" , T.Query(a,b,c,d) );
}
return 0;
}
/*
7 3
aabbabd
1 4 3 6
1 5 5 7
5 6 1 4
Answer:
2
2
1
*/
<后记>