首页 > 代码库 > HDU 4416 Good Article Good sentence（后缀自动机）
HDU 4416 Good Article Good sentence（后缀自动机）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4416
【题目大意】
给出一个字符串，然后，给出一个字符串集合，问在该字符串中出现，且不在字符串集合中出现的子串总数。
【题解】
将集合中所有的子串在自动机上跑，保存匹配到的位置的最长匹配，
用于在parent树上计算每个位置的最长匹配，对于一个位置，
如果不存在匹配，那么他对答案的贡献就是其value值，
如果存在匹配且匹配长度小于其长度那么取其差作为答案的贡献。最后输出即可。
【代码】
#include <cstdio>#include <cstring>#include <algorithm> using namespace std;const int N=200005;char s[N];struct sam{ int p,q,np,nq,cnt,last,a[N][26],l[N],f[N]; sam(){cnt=0;last=++cnt;} int val(int c){return l[c]-l[f[c]];} void init(){ cnt=0;last=++cnt; memset(a,0,sizeof(a)); memset(l,0,sizeof(l)); memset(f,0,sizeof(f)); memset(b,0,sizeof(b)); memset(u,0,sizeof(u)); } void extend(int c){ p=last;np=last=++cnt;l[np]=l[p]+1; while(!a[p][c]&&p)a[p][c]=np,p=f[p]; if(!p)f[np]=1; else{ q=a[p][c]; if(l[p]+1==l[q])f[np]=q; else{ nq=++cnt;l[nq]=l[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); f[nq]=f[q]; f[np]=f[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=f[p]; } } }int b[N],x[N],n; void build(){ scanf("%s",s+1); int len=strlen(s+1);n=len; for(int i=1;i<=len;i++)extend(s[i]-‘a‘); for(int i=1;i<=cnt;i++)b[l[i]]++; for(int i=1;i<=len;i++)b[i]+=b[i-1]; for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i; }int u[N]; void doit(){ scanf("%s",s+1); int p=1,len=strlen(s+1),tmp=0; for(int i=1;i<=len;i++){ int c=s[i]-‘a‘; if(a[p][c])p=a[p][c],tmp++,u[p]=max(u[p],tmp); else{ while(p&&!a[p][c])p=f[p]; if(!p)p=1,tmp=0; else tmp=l[p]+1,p=a[p][c],u[p]=max(u[p],tmp); } } } void solve(){ long long ans=0; for(int i=cnt;i;i--){ if(u[x[i]]){ u[f[x[i]]]=max(u[x[i]],u[f[x[i]]]); if(u[x[i]]<l[x[i]])ans+=l[x[i]]-u[x[i]]; }else ans+=val(x[i]); }printf("%I64d\n",ans); }}sam;int T,n,cas=1;int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); sam.init(); sam.build(); for(int i=1;i<=n;i++)sam.doit(); printf("Case %d: ",cas++); sam.solve(); }return 0;}
HDU 4416 Good Article Good sentence（后缀自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。