로곡 P3796【템플릿】AC자동기(강화판)
22808 단어 AC 로봇
#include //Aho Corasick Automaton
#include
#include
using namespace std;
const int maxn=1000000+3;
const int maxd=20000+3;
const int sigma=30;
char S[maxn],A[160][80];
int mapp[152],times[maxd],val[maxd],last[maxd],f[maxd];
int cnt=0,ans;
queue<int>Q;
struct node{int next[30];}ch[maxd];
int idx(char a){return a-'a';}
struct V{
void insert(char p[],int id){
int n=strlen(p),cur=0;
for(int i=0;i<n;++i){
int u=idx(p[i]);
if(!ch[cur].next[u])ch[cur].next[u]=++cnt;
cur=ch[cur].next[u];
}
++val[cur],mapp[id]=cur;
}
void getfail(){
for(int i=0;i<sigma;++i)if(ch[0].next[i])Q.push(ch[0].next[i]);
while(!Q.empty()){
int r=Q.front(); Q.pop();
for(int i=0;i<sigma;++i){
int u=ch[r].next[i];
if(!u){ch[r].next[i]=ch[f[r]].next[i];continue;}
Q.push(u);int v=f[r];
f[u]=ch[v].next[i];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
}
void print(int j){
if(j){
if(val[j]){++times[j];ans=max(ans,times[j]);}
if(last[j]){
print(last[j]);
}
}
}
void Automaton(char T[]){
int n=strlen(T);int j=0;
for(int i=0;i<n;++i){
int c=idx(T[i]);
j=ch[j].next[c];
print(j);
}
}
}AC;
int main(){
while(1){
int n;scanf("%d",&n);if(!n)return 0;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
memset(last,0,sizeof(last));
memset(f,0,sizeof(f));
memset(times,0,sizeof(times));
cnt=0,ans=0;
for(int i=1;i<=n;++i){scanf("%s",A[i]);AC.insert(A[i],i);}
scanf("%s",S);
AC.getfail();
AC.Automaton(S);
printf("%d
",ans);
for(int i=1;i<=n;++i)
if(times[mapp[i]]==ans)printf("%s
",A[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU4758 Walk Through Squares AC 자동기 & &dp이 문제는 그때 할 때 수론제라고 생각했는데 01열 두 개가 포함돼 있었다. 경기 후에 문자열이라고 듣고 그럴 가능성이 높았다.어제 팀원들이 이 문제를 물었는데 AC자동기를 배운 후에 많이 간단해졌다고 느꼈다.그때는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.