算法模板——AC自动机
2024-10-14 14:40:24
实现功能——输入N，M，提供一个共计N个单词的词典，然后在最后输入的M个字符串中进行多串匹配（关于AC自动机算法，此处不再赘述，详见：Aho-Corasick 多模式匹配算法、AC自动机详解。考虑到有时候字典会相当稀疏，所以引入了chi和bro指针进行优化——其原理比较类似于邻接表，这个东西和next数组本质上是一致的，只是chi和bro用于遍历某一节点下的子节点，next用于查询某节点下是否有需要的子节点）
type
point=^node;
node=record
ex:longint;st:ansistring;
ct:char;
fat,jump,chi,bro:point;
next:array['A'..'Z'] of point;
end;
var
i,j,k,l,m,n:longint;
head,p:point;
s1,s2:ansistring;
function getpoint:point;inline;
var p:point;c1:char;
begin
new(p);
p^.ex:=;p^.st:='';
p^.ct:=chr();
p^.bro:=nil;p^.chi:=nil;
p^.fat:=nil;p^.jump:=head;
for c1:='A' to 'Z' do p^.next[c1]:=nil;
exit(p);
end;
procedure ins(s1:ansistring;x:longint);inline;
var p:point;s2:ansistring;i:longint;
begin
p:=head;S2:='';
for i:= to length(s1) do
begin
s2:=s2+s1[i];
if p^.next[s1[i]]=nil then
begin
p^.next[s1[i]]:=getpoint;
p^.next[s1[i]]^.fat:=p;
p^.next[s1[i]]^.st:=s2;
p^.next[s1[i]]^.ct:=s1[i];
p^.next[s1[i]]^.bro:=p^.chi;
p^.chi:=p^.next[s1[i]];
end;
p:=p^.next[s1[i]];
end;
if p^.ex= then p^.ex:=x;
end;
procedure linkit;inline;
var i,j,k,l,f,r:longint;
d:array[..] of point;
p,p1,p2:point;
begin
f:=;r:=;d[]:=head;
while f<r do
begin
p:=d[f]^.chi;
while p<>nil do
begin
d[r]:=p;
if d[f]<>head then
begin
p1:=d[f]^.jump;
while p1<>head do
begin
if p1^.next[p^.ct]<>nil then break;
p1:=p1^.jump;
end;
if p1^.next[p^.ct]<>nil then p^.jump:=p1^.next[p^.ct];
end;
inc(r);
p:=p^.bro;
end;
inc(f);
end;
end;
procedure fit(s1:ansistring);inline;
var p,p1:point;i:longint;
begin
p:=head;
for i:= to length(s1) do
begin
if p^.next[s1[i]]=nil then
begin
while (p^.next[s1[i]]=nil) and (p<>head) do p:=p^.jump;
if p^.next[s1[i]]<>nil then p:=p^.next[s1[i]];
end
else p:=p^.next[s1[i]];
p1:=p;
while p1<>head do
begin
if p1^.ex<> then writeln('No.',p1^.ex,' ',p1^.st,' From:',i-length(p1^.st)+);
p1:=p1^.jump;
end;
end;
end;
begin
readln(n,m);
head:=getpoint;head^.jump:=head;
for i:= to n do
begin
readln(s1);
ins(upcase(s1),i);
end;
linkit;
for i:= to m do
begin
readln(s1);
fit(upcase(s1));
end;
end.
最新文章
- 整理几种在axure里使页面居中的方法
- 从客户端(txtContent="<p>1</p>")中检测到有潜在危险的 Request.Form 值
- 滚动监听（bootstrap）
- AutoTransformHandler
- JVM学习笔记（三）------内存管理和垃圾回收【转】
- SSL构建单双向https认证
- 对Spring.Net+NHibenate+Asp.Net Mvc+Easyui框架的个人认识
- zabbix 主机名必须要能ping通
- 如何设置文本不换行省略号显示等CSS常用文本属性
- Linux——模拟实现一个简单的shell(带重定向)
- CS（计算机科学）知识体
- C# linq语句学习
- sql-leetcode Consecutive Numbers
- 自学Zabbix5.1 zabbix maintenance维护周期
- C#的委托(delegate、Action、Func、predicate)
- [Golang] 第三方包应该如何安装--在线和离线
- keras自定义padding大小
- Windows下使用MakeFile(Mingw)文件
- 解决eclipse中断点调试不起作用的问题
- C#应用视频教程2.1 OPENGL虚拟仿真介绍