题解 SP220 【PHRASES - Relevant Phrases of Annihilation】

万弘

2020-08-20 12:44:51

Solution

来一篇广义后缀树的题解. 先建好广义后缀树,那么每个子串都恰属于广义后缀树的一个节点.对于每个点 $ 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; } ```