题解 SP220 【PHRASES - Relevant Phrases of Annihilation】
万弘
2020-08-20 12:44:51
来一篇广义后缀树的题解.
先建好广义后缀树,那么每个子串都恰属于广义后缀树的一个节点.对于每个点 $ u $ 我们要统计出 $ u $ 表示的状态在每个串中的最早位置 $ st $ 与最晚位置 $ ed $ (如果对于每个串都满足 $ ed-st\ge len(u) $,那么就是可行的,因此我们只要记每个串中的最早位置与最晚位置而非所有位置).
如果按照套路,是用线段树合并求出在哪些串中出现了,但是我们还要求每个串都满足 $ ed-st\ge len(u) $ ,而后缀树上父子的状态长度显然不同,就没办法快速维护了.
我的处理方法是,用 $ \text{Dsu on tree} $ .直接维护 $ st_i,ed_i $ 表示当前状态在第 $ i $ 个串的最早位置与最晚位置,暴力轻儿子,继承重儿子,只要做 $ \mathcal O(L\log L) $ 次加入一个点的贡献的操作.加入该点的贡献就把以该点为终止点的串的 $ st,ed $ 都修改就好了,同时用栈存下每次操作,便于清空轻儿子的贡献. $ n\le 10 $ ,所以暴力扫每个串去判断就好了.时间复杂度 $ \mathcal O(nL\log L) $ .
如果 $ n $ 比较大,可以用平衡树维护 $ ed-st $ 的最小值.时间复杂度 $ \mathcal O(L\log L\log n) $ .
注意广义后缀树上一个点代表多个串,虽然endpos集合相同但长度不同,要选尽量长的去更新答案.
```cpp
#define MAXN 400011
std::multiset<int>bst;
struct SAM
{
int t[MAXN][26],pre[MAXN],len[MAXN];
int last,tot;
SAM(){last=tot=1;}
void insert(int w)
{
if(t[last][w])
{
int nxt=t[last][w];
if(len[nxt]==len[last]+1)last=nxt;
else
{
int tmp=++tot;
len[tmp]=len[last]+1;
memcpy(t[tmp],t[nxt],sizeof t[nxt]);
pre[tmp]=pre[nxt],pre[nxt]=tmp;
while(last&&t[last][w]==nxt)t[last][w]=tmp,last=pre[last];
last=tmp;
}
return;
}
int pos=last,cur=++tot;
len[cur]=len[pos]+1,last=cur;
while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
if(!pos){pre[cur]=1;return;}
int nxt=t[pos][w];
if(len[nxt]==len[pos]+1)pre[cur]=nxt;
else
{
int tmp=++tot;
len[tmp]=len[pos]+1;
memcpy(t[tmp],t[nxt],sizeof t[nxt]);
pre[tmp]=pre[nxt],pre[nxt]=pre[cur]=tmp;
while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
}
}
std::vector<int>g[MAXN];
std::vector<pii>endp[MAXN];
int size[MAXN], mson[MAXN];
void dfs1(int u)
{
size[u]=1,mson[u]=0;
for(auto v:g[u])
{
if(v==pre[u])continue;
dfs1(v),size[u]+=size[v];
if(size[v]>size[mson[u]])mson[u]=v;
}
}
struct one{int num,st,ed;}s[MAXN];
int top=0,st[MAXN],ed[MAXN],ans=0;
void back(int t)
{
while(top>t)
{
int x=s[top].num;
bst.erase(bst.lower_bound(ed[x]-st[x]));
ed[x]=s[top].ed,st[x]=s[top].st;--top;
bst.insert(ed[x]-st[x]);
// printf("Back f[%d] to [%d,%d]\n",x,st[x],ed[x]);
}
}
void push(int u)
{
for(auto x:endp[u])
{
int num=x.first,now=x.second;
bst.erase(bst.lower_bound(ed[num]-st[num])),s[++top]=one{num,st[num],ed[num]};
umin(st[num],now),umax(ed[num],now);
bst.insert(ed[num]-st[num]);
// printf("modify f[%d] to [%d,%d]\n",num,st[num],ed[num]);
}
for(auto v:g[u])
if(v!=pre[u])push(v);
}
void solve(int u)
{
int t;
for(auto v:g[u])
if(v!=pre[u]&&v!=mson[u])t=top, solve(v),back(t);
if(mson[u])solve(mson[u]);
for(auto x:endp[u])
{
int num=x.first,now=x.second;
bst.erase(bst.lower_bound(ed[num]-st[num])),s[++top]=one{num,st[num],ed[num]};
umin(st[num],now),umax(ed[num],now);
bst.insert(ed[num]-st[num]);
// printf("modify f[%d] to [%d,%d]\n",num,st[num],ed[num]);
}
for(auto v:g[u])
if(v!=pre[u]&&v!=mson[u])push(v);
// printf("len[%d]=%d,mind=%d,size=%d\n",u,len[u],*bst.begin(),int(bst.size()));
if((*bst.begin())>len[pre[u]])umax(ans,min(len[u],*bst.begin()));
}
int Query(int n)
{
// printf("pre[4]=%d,size[4]=%d\n",pre[4],size[4]);
ans=0;
for(int i=2;i<=tot;++i)g[pre[i]].push_back(i);
dfs1(1);
// printf("pre[4]=%d,size[4]=%d\n",pre[4],size[4]);
// printf("mson[14]=%d,size[10]=%d\n",mson[14],size[10]);
for(int i=1;i<=n;++i)st[i]=20000,ed[i]=0,bst.insert(ed[i]-st[i]);
solve(1);
for(int i=1;i<=tot;++i)g[i].clear(),endp[i].clear();
memset(t,0,sizeof t),memset(pre,0,sizeof pre),memset(len,0,sizeof len);
last=tot=1;top=0;
bst.clear();
return ans;
}
}sam;
char s[MAXN];
int main()
{
int task=read();
while(task--)
{
int n=read();
for(int i=1;i<=n;++i)
{
sam.last=1;
scanf("%s",s+1);
int l=strlen(s+1);
for(int j=1;j<=l;++j)sam.insert(s[j]-'a'),sam.endp[sam.last].push_back(pii(i,j));
}
printf("%d\n",sam.Query(n));
}
return 0;
}
```