【模板】AC自动机

2019-04-13 20:39发布

站内文章 / 模拟电子
10466 0 1037
传送门 //by sdfzchy #include #include #include #include #include using namespace std; typedef long long LL; const int inf=(1<<30),N=1000010; int n,m; struct AC_automaton { int ch[26],fail,cnt; }t[N]; inline int in() { char ch=getchar(); int f=1,tmp=0; while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();} return tmp*f; } char s[N]; int ans,cnt; void ins() { int u=0,v,len=strlen(s); for(int i=0;iint c=s[i]-'a'; if(!t[u].ch[c]) t[u].ch[c]=++cnt; u=t[u].ch[c]; } t[u].cnt++; } queue<int> q; void gi_fail() { for(int i=0;i<26;i++) if(t[0].ch[i]) q.push(t[0].ch[i]),t[t[0].ch[i]].fail=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<26;i++) { int &v=t[u].ch[i]; if(v) t[v].fail=t[t[u].fail].ch[i],q.push(v); else v=t[t[u].fail].ch[i]; } } } void gi_sol() { int u=0,v,c,len=strlen(s); for(int i=0;i'a'; u=t[u].ch[c]; for(int j=u;t[j].cnt!=-1;j=t[j].fail) { ans+=t[j].cnt; t[j].cnt=-1; } } } int main() { n=in(); for(int i=1;i<=n;i++) scanf("%s",s),ins(); gi_fail(); scanf("%s",s); gi_sol(); printf("%d ",ans); return 0; } 传送门 //by sdfzchy #include #include #include #include #include using namespace std; typedef long long LL; const int inf=(1<<30),N=1000100; int n,m; inline int in() { char ch=getchar(); int f=1,tmp=0; while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();} return tmp*f; } struct AC_atm { int ch[26],fail,id; }t[N]; char s[200][100]; int tot; void ins(char *s,int id) { int c,u=0,len=strlen(s); for(int i=0;i'a'; if(!t[u].ch[c]) t[u].ch[c]=++tot; u=t[u].ch[c]; } t[u].id=id; } queue<int> q; void gi_fail() { while(!q.empty()) q.pop(); for(int i=0;i<26;i++) if(t[0].ch[i]) q.push(t[0].ch[i]),t[t[0].ch[i]].fail=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<26;i++) { int &v=t[u].ch[i]; if(v) t[v].fail=t[t[u].fail].ch[i],q.push(v); else v=t[t[u].fail].ch[i]; } } } char S[N]; int ans,cnt[N]; void gi_sol() { int u=0,c,len=strlen(S); for(int i=0;i'a'; u=t[u].ch[c]; for(int j=u;j;j=t[j].fail) if(t[j].id) cnt[t[j].id]++; } } int main() { while(n=in()) { memset(t,0,sizeof(t)); memset(cnt,0,sizeof(cnt)); ans=0; for(int i=1;i<=n;i++) scanf("%s",s[i]),ins(s[i],i); scanf("%s",S); gi_fail(); gi_sol(); for(int i=1;i<=n;i++) ans=max(ans,cnt[i]); printf("%d ",ans); for(int i=1;i<=n;i++) if(cnt[i]==ans) printf("%s ",s[i]); } return 0; }

热门文章