完全忘了 AC 自动机怎么写了 qwq, 更别说 AC 自动机上 DP 了.
今天就好好地学习字符串好了 qwq
简单版: 给定一个文本串, 和多个模式串. 求有多少个模式串在文本串中出现过. qwqwq
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<queue>
- #define MAXN 1000010
- using namespace std;
- int cnt,n;
- char s[MAXN];
- struct tree{int fail,end,t[26];}ac[MAXN];
- inline void build(char s[])
- {
- int len=strlen(s);
- int now=0;
- for(int i=0;i<len;i++)
- {
- if(!ac[now].t[s[i]-'a'])
- ac[now].t[s[i]-'a']=++cnt;
- now=ac[now].t[s[i]-'a'];
- }
- ac[now].end+=1;
- }
- inline void get_fail()
- {
- queue<int>q;
- for(int i=0;i<=25;i++)
- if(ac[0].t[i]!=0)
- ac[ac[0].t[i]].fail=0,q.push(ac[0].t[i]);
- while(!q.empty())
- {
- int u=q.front();q.pop();
- for(int i=0;i<=25;i++)
- {
- if(ac[u].t[i]!=0)
- {
- ac[ac[u].t[i]].fail=ac[ac[u].fail].t[i];
- q.push(ac[u].t[i]);
- }
- else ac[u].t[i]=ac[ac[u].fail].t[i];
- }
- }
- }
- inline int ac_query(char s[])
- {
- int len=strlen(s);
- int now=0,ans=0;
- for(int i=0;i<len;i++)
- {
- int now=ac[now].t[s[i]-'a'];
- for(int k=now;k&&ac[k].end!=-1;k=ac[k].fail)
- ans+=ac[k].end,ac[k].end=-1;
- }
- return ans;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("ce.in","r",stdin);
- #endif
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",s);
- build(s);
- }
- ac[0].fail=0;
- get_fail();
- scanf("%s",s);
- printf("%d\n",ac_query(s));
- }
加强版: 给定一个文本串和许多模式串, 问在文本串中出现次数最多的模式串? 以及出现的次数.
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #define MAXN 1000010
- using namespace std;
- int cnt,n;
- char s[1000][100],q[MAXN];
- struct tree{int fail,end,t[26];}ac[MAXN];
- struct Ans{int num,pos;}ans[MAXN];
- inline bool cmp(struct Ans x,struct Ans y)
- {
- if(x.num!=y.num) return x.num>y.num;
- else return x.pos<y.pos;
- }
- inline void clean(int x)
- {
- memset(ac[x].t,0,sizeof(ac[x].t));
- ac[x].fail=ac[x].end=0;
- }
- inline void build(char s[],int num)
- {
- int len=strlen(s),now=0;
- for(int i=0;i<len;i++)
- {
- if(ac[now].t[s[i]-'a']==0)
- ac[now].t[s[i]-'a']=++cnt,clean(cnt);
- now=ac[now].t[s[i]-'a'];
- }
- ac[now].end=num;
- }
- inline void get_fail()
- {
- queue<int>q;
- for(int i=0;i<=25;i++)
- {
- if(ac[0].t[i]!=0)
- ac[ac[0].t[i]].fail=0,q.push(ac[0].t[i]);
- }
- while(!q.empty())
- {
- int u=q.front();q.pop();
- for(int i=0;i<=25;i++)
- {
- if(ac[u].t[i]!=0)
- {
- ac[ac[u].t[i]].fail=ac[ac[u].fail].t[i];
- q.push(ac[u].t[i]);
- }
- else ac[u].t[i]=ac[ac[u].fail].t[i];
- }
- }
- }
- inline void ac_query(char s[])
- {
- int len=strlen(s),now=0;
- for(int i=0;i<len;i++)
- {
- now=ac[now].t[s[i]-'a'];
- for(int k=now;k;k=ac[k].fail)
- ans[ac[k].end].num++;
- }
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("ce.in","r",stdin);
- #endif
- scanf("%d",&n);
- for(;;)
- {
- if(n==0) break;
- cnt=0;
- clean(0);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",s[i]);
- ans[i].num=0,ans[i].pos=i;
- build(s[i],i);
- }
- ac[0].fail=0;
- get_fail();
- scanf("%s",q);
- ac_query(q);
- sort(&ans[1],&ans[n+1],cmp);
- printf("%d\n",ans[1].num);
- int len=strlen(s[ans[1].pos]);
- for(int i=0;i<len;i++) printf("%c",s[ans[1].pos][i]);
- puts("");
- for(int i=2;i<=n;i++)
- {
- if(ans[i].num==ans[1].num)
- {
- int lenth=strlen(s[ans[i].pos]);
- for(int j=0;j<lenth;j++) printf("%c",s[ans[i].pos][j]);puts("");
- }
- else break;
- }
- scanf("%d",&n);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2957446.html