首页 > 代码库 > 【BZOJ3238】【Ahoi2013】差异 后缀自动机
【BZOJ3238】【Ahoi2013】差异 后缀自动机
转载请注明出处谢谢、、http://blog.csdn.net/vmurder/article/details/42721101
首先 秦神QY Orz
题解:
这道题后缀数组过于鬼畜(wo’tai’ruo’bu’gan’xie)
所以写了简单好写易于理解不用分治不用RMQ的SAM大叔。
题解:
首先其实我们需要一个后缀树,然后两个后缀的lcp就是它们lca的len。
后缀树可以通过反序后缀自动机得到,这个很水。
然后len的性质就是后缀自动机的那个len(我写的‘deep’)。
后缀树上DP就水了,随便乱搞就可以过了。
那个size[x]*size[x-1]是C(size[x],2)的意思。
分析:一个节点(状态)的deep就是以他为结束的最长子串长度,当然就是那个lca了233。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1001000 #define T 26 using namespace std; struct KSD { int v,next; }e[N]; int head[N],cnt; inline void add(int u,int v) { cnt++; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } int size[N]; int pa[N],son[N][T],dep[N]; int tot=1,last=1; inline int newnode(int _dep){dep[++tot]=_dep;return tot;} inline void SAM(int alp) { int p=newnode(dep[last]+1); size[p]=1; int u=last; while(u&&!son[u][alp])son[u][alp]=p,u=pa[u]; if(!u)pa[p]=1; else { int v=son[u][alp]; if(dep[v]==dep[u]+1)pa[p]=v; else { int nv=newnode(dep[u]+1); pa[nv]=pa[v],pa[v]=pa[p]=nv; memcpy(son[nv],son[v],sizeof son[nv]); while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u]; } } last=p; } long long ans; void tree_dp(int x,int p) { int i,v; for(i=head[x];i;i=e[i].next) { tree_dp(v=e[i].v,x); size[x]+=size[v]; } dep[x]-=dep[p]; ans-=(long long)size[x]*(size[x]-1)*dep[x]; } char str[N]; int main() { // freopen("test.in","r",stdin); int i,j,k; scanf("%s",str); int len=strlen(str); for(i=len-1;i>=0;i--)SAM(str[i]-'a'); ans=(long long)(len-1)*len*(len+1)>>1; for(i=2;i<=tot;i++)add(pa[i],i); for(i=head[1];i;i=e[i].next)tree_dp(e[i].v,1); cout<<ans<<endl; return 0; }
【BZOJ3238】【Ahoi2013】差异 后缀自动机
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。