正解: AC 自动机
解题报告:
传送门! https://www.luogu.org/problemnew/show/P3966
先来提供一个 40pts 错解 QAQ
首先看到这题就会想到 AC 自动机板子题 2 鸭! 然后就照着那题的套路打一下, 随便改一点儿, 简单来说就是每次经过一个节点都要 ++, 然后每搜到一个节点就暴跳所有 fail,tr[fail].as+=tr[nw].as
然后你就能得到 40pts 的好成绩,,, 另外 60pts 还是 WA 的,,, 就很难过,,,
- #include<bits/stdc++.h>
- using namespace std;
- #define ll int
- #define rp(i,x,y) for(register ll i=x;i<=y;++i)
- const ll N=1000000+100,M=200+10;
- ll n,cnt,as,ed[M];
- struct tre{ll as,nxt[27],fail;tre(){as=0;memset(nxt,0,sizeof(nxt));fail=0;}}tr[N];
- bool gdgs=1;
- inline ll read()
- {
- register char ch=getchar();register ll x=0;register bool y=1;
- while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
- if(ch=='-')ch=getchar(),y=0;
- while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
- return y?x:-x;
- }
- inline void bd(ll nm)
- {
- string str;cin>>str;ll lth=str.length()-1,nw=0;
- rp(i,0,lth)
- {
- if(tr[nw].nxt[str[i]-'a'+1]==0)tr[nw].nxt[str[i]-'a'+1]=++cnt;
- nw=tr[nw].nxt[str[i]-'a'+1];++tr[nw].as;
- }
- ed[nm]=nw;
- }
- inline void fl()
- {
- queue<ll>Q;
- rp(i,1,26)if(tr[0].nxt[i])Q.push(tr[0].nxt[i]);
- while(!Q.empty())
- {
- ll nw=Q.front();Q.pop();
- rp(i,1,26)
- {
- if(tr[nw].nxt[i])tr[tr[nw].nxt[i]].fail=tr[tr[nw].fail].nxt[i],Q.push(tr[nw].nxt[i]);
- else tr[nw].nxt[i]=tr[tr[nw].fail].nxt[i];
- }
- }
- }
- inline void zdj()
- {
- rp(i,1,cnt)
- {
- // printf("i=%d as=%d\n",i,tr[i].as);
- for(register ll j=i;j;j=tr[j].fail)tr[tr[j].fail].as+=tr[i].as/*,printf("j=%d fl=%d\n",j,tr[j].fail)*/;
- }
- }
- int main()
- {
- n=read();rp(i,1,n)bd(i);fl();tr[0].fail=0;zdj();//printf("QAQ?\n");
- rp(i,1,n)printf("%d\n",tr[ed[i]].as);
- return 0;
- }
放下 sd 灵巧的 sd 代码呜呜呜
研究辣半天回来 repo 一下我错哪儿辣,,, 我好像是打挂辣呜呜呜
不过还是有个点有问题
就是, 暴跳会 T
可以先走出 bfs 序, 然后直接按 bfs 序每次就只有这个点的 fail 要跳辣而不是所有的 fail 都要跳一遍
然后就 over 辣!
话说为什么这题居然有紫,,,? 病毒都比这题难一些啊我 jio 得,,,?
等下放代码 QAQ
来源: http://www.bubuko.com/infodetail-2946502.html