[题解] [P2444 POI2000] 病毒 https://www.luogu.org/problemnew/show/P2444
一道 \(ac\) 自动机好题...
考虑危险的字符串是什么意思, 就是在这个文本串中有模式串的匹配, 这样的匹配可以通过 \(ac\) 自动机完成.
那么给定一个字符串如何判断是否有病毒, 直接就是看 ac 自动机是否匹配成功.
考虑 "无限长的安全字符串" 代表什么意思, 就是在 \(ac\) 自动机找到一个环. 可以用阉割版的 \(tarjin\)
- #include<bits/stdc++.h>
- using namespace std;
- #define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
- #define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
- #define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
- #define Max(a,b) ((a)<(b)?(b):(a))
- #define Min(a,b) ((a)<(b)?(a):(b))
- #define midd register int mid=(l+r)>>1
- #define TMP template <class ccf>
- TMP inline ccf qr(ccf b){
- char c=getchar();
- int q=1;
- ccf x=0;
- while(c<48||c>57)
- q=c==45?-1:q,c=getchar();
- while(c>=48&&c<=57)
- x=x*10+c-48,c=getchar();
- return q==-1?-x:x;
- }
- const int maxac=30005;
- int n;
- string x;
- struct AC{
- int son[2];
- int fail;int cnt;
- inline int& operator [](int o){
- return son[o&1];
- }
- inline int& operator [](char o){
- return son[(o-'0')&1];
- }
- }ac[maxac];
- int act;
- inline void build(int lit){
- int now=0;
- RP(t,0,lit-1){
- if(!ac[now][x[t]])
- ac[now][x[t]]=++act;
- now=ac[now][x[t]];
- }
- ac[now].cnt++;
- //cout<<"build="<<now<<endl;
- }
- queue<int> q;
- inline void gen(){
- RP(t,0,1)
- if(ac[0][t])
- q.push(ac[0][t]);
- while(!q.empty()){
- int now=q.front();
- q.pop();
- RP(t,0,1){
- if(ac[now][t]){
- ac[ac[now][t]].fail=ac[ac[now].fail][t];
- ac[ac[now][t]].cnt|=ac[ac[ac[now].fail][t]].cnt;
- q.push(ac[now][t]);
- }
- else
- ac[now][t]=ac[ac[now].fail][t];
- }
- }
- }
- bool in[maxac];
- bool usd[maxac];
- void dfs(int now){
- usd[now]=in[now]=1;
- RP(t,0,1){
- if(in[ac[now][t]])
- puts("TAK"),exit(0);
- if(!ac[ac[now][t]].cnt)
- dfs(ac[now][t]);
- }
- in[now]=0;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in.in","r",stdin);
- freopen("out.out","w",stdout);
- #endif
- n=qr(1);
- RP(t,1,n){
- cin>>x;
- build(x.length());
- }
- gen();
- if(!ac[0].cnt)
- dfs(0);
- puts("NIE");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2946951.html