bzoj2938

显然AC自动机,但什么叫无限生成呢?
显然就是在AC自动机上匹配,出现了一个环(不能走结尾节点)
直接搜索即可

 var trie:array[..,''..''] of longint;
q,f:array[..] of longint;
can,v,r:array[..] of boolean;
l,n,i,t,j,k:longint;
s:ansistring; procedure ac;
var j,x,y,h,r:longint;
c:char;
begin
h:=;
r:=;
for c:='' to '' do
if trie[,c]<> then
begin
inc(r);
q[r]:=trie[,c];
end;
while h<=r do
begin
x:=q[h];
for c:='' to '' do
if trie[x,c]<> then
begin
y:=trie[x,c];
inc(r);
q[r]:=y;
j:=f[x];
while (j>) and (trie[j,c]=) do j:=f[j];
f[y]:=trie[j,c];
if can[trie[j,c]] then can[y]:=true;
end;
inc(h);
end;
end; function dfs(x:longint):boolean;
var c:char;
j:longint;
begin
if can[x] then exit(false);
if v[x] then exit(true)
else v[x]:=true;
for c:='' to '' do
begin
j:=x;
while (j>) and (trie[j,c]=) do j:=f[j];
if r[trie[j,c]] then continue;
if dfs(trie[j,c]) then exit(true);
end;
v[x]:=false;
r[x]:=true;
exit(false);
end; begin
readln(n);
t:=;
for i:= to n do
begin
readln(s);
l:=length(s);
j:=;
for k:= to l do
begin
if trie[j,s[k]]= then
begin
inc(t);
trie[j,s[k]]:=t;
end;
j:=trie[j,s[k]];
end;
can[j]:=true;
end;
ac;
if dfs() then writeln('TAK') else writeln('NIE');
end.
上一篇:linux的基本操作(LNMP的基本操作)


下一篇:mysql 错误代码:1118解决方法