首页 > 代码库 > BZOJ 2780: [Spoj]8093 Sevenk Love Oimaster [广义后缀自动机]

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

2024-09-03 16:36:11   207人阅读

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中给出的方法 
还有一种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 [广义后缀自动机]


联系
我们