BZOJ 2780 [Spoj]8093 Sevenk Love Oimaster ——广义后缀自动机-白红宇

BZOJ 2780 [Spoj]8093 Sevenk Love Oimaster ——广义后缀自动机

阅读量：6001 次

发布时间：2019-06-20

本文共 2300 字，大约阅读时间需要 7 分钟。

给定n个串m个询问，问每个串在n个串多少个串中出现了。

构建广义后缀自动机，（就是把所有字符串的后缀自动机合并起来）其实只需要add的时候注意一下就可以了。

然后对于每一个串，跑一边匹配，到达了now点。

如果now等于零，那么无法匹配，为0

否则就是询问子树中属于不同的后缀的节点又多少个。

如果n的数目比较小，可以考虑O(nl)去树形DP

我们只能，用vector打上标记。

然后dfs序搞出来，然后就是区间不同数的计数问题，然后直接《HH的项链》这道题目一套就可以了。

这一题套一题确实很有趣，代码丑到爆炸

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define maxn 500005 int in[maxn],out[maxn],tot,lst[maxn],ans[maxn];int arr[maxn],pos[maxn],top,nxt[maxn]; struct Query{ int l,r,id; void print() { printf("Query About %d to %d\n",l,r); }}brr[maxn]; struct Generalized_Suffix_Automaton{ int h[maxn],to[maxn],ne[maxn],en; char s[maxn]; int last,cnt,n,q; map
           
            go[maxn]; int l[maxn],fa[maxn]; vector
            
             v[maxn]; void init(){last=cnt=1;memset(h,-1,sizeof h);} void addedge(int a,int b) {to[en]=b;ne[en]=h[a];h[a]=en++;} void add(int x,int id) { int p=last,q; if (q=go[p][x]) { if (l[p]+1==l[q]) last=q; else { int nq=++cnt; l[nq]=l[p]+1; go[nq]=go[q]; fa[nq]=fa[q]; fa[q]=nq; for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq; last=nq; } } else { int np=++cnt; l[np]=l[p]+1; for (;p&&!go[p][x];p=fa[p]) go[p][x]=np; if (!p) fa[np]=1; else { q=go[p][x]; if (l[q]==l[p]+1) fa[np]=q; else { int nq=++cnt;l[nq]=l[p]+1; go[nq]=go[q]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq; } } last=np; } v[last].push_back(id); } void dfs(int k) { in[k]=++tot; for (int i=0;i
             
              =0;i=ne[i]) dfs(to[i]); out[k]=tot; } void solve() { init(); scanf("%d%d",&n,&q); F(i,1,n) { last=1; scanf("%s",s+1); int len=strlen(s+1); F(j,1,len) add(s[j],i); } F(i,1,cnt) addedge(fa[i],i); dfs(1); F(i,1,q) { scanf("%s",s+1); int len=strlen(s+1);// printf("%s\n",s+1);// F(j,1,len) printf("-%c-",s[j]); printf("\n"); int now=1; F(j,1,len){now=go[now][s[j]];}// printf("now is %d\n",now); if (now) { ++top; brr[top].l=in[now]; brr[top].r=out[now]; brr[top].id=i; } } }}sam; struct Bit_Tree{ int x[maxn]; void add(int pos,int del) {for (;pos<=tot;pos+=pos&(-pos)) x[pos]+=del;} int query(int pos) {int ret=0;for (;pos;pos-=pos&(-pos))ret+=x[pos];return ret;}}BT; bool cmp(Query a,Query b){return a.l==b.l?a.r