bzoj 2938
收获：
1、AC自动机可以在建立fail时将一些不存在的儿子指针指向对应的位置。
2、判断环时不要想当然地写个这样的版本：
bool dfs( int u ) {
if( vis[u] ) return true;
vis[u] = true;
for( int t=0; t<g[u].size(); t++ ) {
int v=g[u][t];
if( dfs(v) ) return true;
}
vis[u] = false;
return false;
}
原因大概是因为没有考虑下一个点可能已经处理过
它不是O(n)的，然后我就T了，搞了好久才弄好。
3、存在一个无限长的不与给定pattern匹配的text，那么在该text上跑ac自动机会无限循环，反之一定会在有限的时间内结束。
/**************************************************************
Problem: 2938
User: idy002
Language: C++
Result: Accepted
Time:40 ms
Memory:2316 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define maxn 60010
using namespace std;
int son[maxn][2], fail[maxn], ikey[maxn], ntot;
int vis[maxn], cir[maxn];
char str[maxn];
void insert( const char *P ) {
int n=strlen(P);
int u=0;
for( int i=0; i<n; i++ ) {
int c=P[i]-'0';
if( !son[u][c] ) son[u][c] = ++ntot;
u=son[u][c];
}
ikey[u] = true;
}
void build_fail() {
queue<int> qu;
for( int c=0; c<2; c++ ) {
int v=son[0][c];
if( !v ) continue;
qu.push( v );
fail[v] = 0;
}
while( !qu.empty() ) {
int u=qu.front();
qu.pop();
for( int c=0; c<2; c++ ) {
int v=son[u][c];
int w=fail[u];
if( !v ) {
son[u][c] = son[fail[u]][c];
continue;
}
while( w && !son[w][c] ) w=fail[w];
fail[v] = son[w][c];
ikey[v] |= ikey[fail[v]];
qu.push( v );
}
}
}
void dfs( int u ) {
vis[u] = true;
for( int c=0; c<2; c++ ) {
int v=son[u][c];
if( cir[v] || ikey[v] ) continue;
if( !vis[v] )
dfs(v);
else {
printf( "TAK\n" );
exit(0);
}
}
cir[u] = true;
}
int main() {
int n;
scanf( "%d", &n );
for( int i=0; i<n; i++ ) {
scanf( "%s", str );
insert( str );
}
build_fail();
dfs( 0 );
printf( "NIE\n" );
}
评论