首页 > 代码库 > 【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster
Description
Oimaster and sevenk love each other.
Input
There are two integers in the first line, the number of strings n and the number of questions q.And n lines follow, each of them is a string describing oimaster‘s online talk. And q lines follow, each of them is a question.n<=10000, q<=60000 the total length of n strings<=100000, the total length of q question strings<=360000
Output
For each question, output the answer in one line.
Sample Input
3 3
abcabcabc
aaa
aafe
abc
a
ca
abcabcabc
aaa
aafe
abc
a
ca
Sample Output
1
3
1
3
1
题意:给你一堆文本串,每次询问一个串在多少个文本串中出现过。
题解:多串匹配要用到广义SAM。就是在每当开始加入一个串的时候,将last指针变回root。
那么这题怎么搞?我们需要知道SAM中的每个节点被多少个文本串所包含。记录sum[i]表示i被多少个文本串包含,vis[i]表示当前时刻,最后一个包含i的文本串是哪个。在建完SAM后,我们将所有串在SAM上再跑一边,将经过的点,以及它的parent树上的所有祖先都更新一遍(因为一个点被影响后它的所有parent也要被影响),如果某个点的vis=当前时间,则退出,否则更新sum和vis。
时间复杂度我不太会证,大概O(nsqrt(n))吧?不过这题也有O(nlogn)的做法,就是求出parent树的DFS序,每次询问相当于问一个点在parent树的子树中有多少个不同的文本串,也就转换成在DFS序上的一段区间中有多少个不同的文本串。这个显然是HH的项链啊,不过感觉好麻烦。(懒)
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,tot;int pre[400010],ch[400010][26],mx[400010],s[400010],vis[400010],lp[400010],rp[400010];char str[800010];void updata(int x,int y){ for(;x&&vis[x]!=y;x=pre[x]) s[x]++,vis[x]=y;}int extend(int x,int y,int p){ int np=++tot; mx[np]=mx[p]+1; for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np; if(!p) pre[np]=1; else { int q=ch[p][x]; if(mx[q]==mx[p]+1) pre[np]=q; else { int nq=++tot; pre[nq]=pre[q],pre[np]=pre[q]=nq,mx[nq]=mx[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq; } } return np;}int main(){ scanf("%d%d",&n,&m); int i,j,a,b; tot=1; for(i=1;i<=n;i++) { lp[i]=rp[i-1]; scanf("%s",str+lp[i]); rp[i]=strlen(str); for(b=1,j=lp[i];j<rp[i];j++) b=extend(str[j]-‘a‘,i,b); } for(i=1;i<=n;i++) for(a=1,j=lp[i];j<rp[i];j++) a=ch[a][str[j]-‘a‘],updata(a,i); for(i=1;i<=m;i++) { scanf("%s",str); a=strlen(str); for(b=1,j=0;j<a;j++) { if(ch[b][str[j]-‘a‘]) b=ch[b][str[j]-‘a‘]; else break; } if(j==a) printf("%d\n",s[b]); else printf("0\n"); } return 0;}
【BZOJ2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。