首页 > 代码库 > BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster [广义后缀自动机]
BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster [广义后缀自动机]
JZPGYZ - Sevenk Love Oimaster
Oimaster and sevenk love each other. But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman‘s nature, sevenk felt angry and began to check oimaster‘s online talk with ChuYuXun. Oimaster talked with ChuYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, "how many strings in oimaster‘s online talk contain this string as their substrings?"
这篇文章讲述了一个sevenk如何用后缀自动机检查Oimaster的聊天记录......
题意:给出很多主串和很多询问串,求一个询问串在主串中出现次数
裸题啊.....除了我在http://www.cnblogs.com/candy99/p/sam.html中给出的方法
这篇文章讲述了一个sevenk如何用后缀自动机检查Oimaster的聊天记录......
题意:给出很多主串和很多询问串,求一个询问串在主串中出现次数
裸题啊.....除了我在http://www.cnblogs.com/candy99/p/sam.html中给出的方法
还有一种NlogN的做法,求出Parent树DFS序然后就是区间询问多少种不同的颜色,HH的项链.....注意一个点会有多种颜色
注意string别用错
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#include <string>using namespace std;const int N=2e5+5,M=1e4+5;typedef long long ll;int n,Q;string ss[M];char s[N<<1];struct node{ int ch[26],par,val; int cou,cur;}t[N];int sz=1,root=1,last=1;void extend(int c){ int p=last,np=++sz; t[np].val=t[p].val+1; for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np; if(!p) t[np].par=root; else{ int q=t[p].ch[c]; if(t[q].val==t[p].val+1) t[np].par=q; else{ int nq=++sz; t[nq]=t[q];t[nq].val=t[p].val+1; t[q].par=t[np].par=nq; for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq; } } last=np;}void solve(){ int u; for(int i=1;i<=n;i++){ u=root; string &s=ss[i]; for(int j=0;j<s.size();j++){ u=t[u].ch[s[j]-‘a‘]; int p=u; for(;p&&t[p].cur!=i;p=t[p].par) t[p].cou++,t[p].cur=i; } } while(Q--){ scanf("%s",s); int n=strlen(s),u=root,flag=0; for(int i=0;i<n;i++){ int c=s[i]-‘a‘; if(t[u].ch[c]) u=t[u].ch[c]; else{flag=1;break;} } if(flag) puts("0"); else printf("%d\n",t[u].cou); }}int main(){ freopen("in","r",stdin); scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++){ scanf("%s",s); ss[i]=string(s); last=root; int len=ss[i].size(); for(int j=0;j<len;j++) extend(s[j]-‘a‘); } solve();}
BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster [广义后缀自动机]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。