字符串（3）AC自动机
AC自动机真神奇，其实说白了就是在trie树上进行kmp模式匹配，不过刚接触确实有些难度，有些思想确实有些难以理解，所以学习的时候最好亲自手动模拟整个算法的全过程，那我就来写篇blog总结一下。
首先我们需要明白AC自动机是用来干什么的，首先我们知道kmp算法是用来解决单模式串匹配问题的，那么如果模式串不止一个，我们该怎么办呢？没错，AC自动机。我们可以把所有的模式串建立一棵字典树，然后在字典树上进行自我匹配建立next数组，最后利用next数组与主串进行匹配。
建立trie树没有什么问题，最难的地方估计是建立next数组的过程，那我就来手动模拟一下。
假设模式串为：AAAA ABA BBA BBB
主串为：AAAABBABABABB
首先我们建立字典树：
不过AC自动机里的字典树和普通的trie有所不同，这里的trie定义了一个0号虚结点，并且0号结点的所有出边都连向一号点，也就是说我们可以理解为1号结点代表的所有的字符集，然后我们将一号点的next指向0号点。
对于2号结点，我们有f[2]=1（其中f[i]表示i结点的父结点）那么我们就看一下1号点的next指向的0号点是否含有A这个儿子。显然1号结点就是这样的结点，所以2号点的next连向1。
同样的我们对于三号点也进行同样的操作，由于一号点的next是0，而0有B这样的儿子，所以把3的next连向1。
对于其余的结点我们也进行一样的操作：
但是对于8号点，它的父亲是5号点，5号点的next为3号点，然而三号点没有A这个儿子结点，那我们就继续查询3号点的next 1号点，一号点有A这个儿子，所以把8号点的next指向2号点。
然后我们就可以建立整棵trie树的next数组了。
这里有一个问题，我们在询问8号点时，重复跳了几次next这样便使得时间复杂度超过我们期望的O（n），所以我们需要进行一些神奇的操作。
我们在询问三号结点A这个儿子的时候，由于它不存在，一般情况我们就会continue，然后继续询问他的其它儿子，但是我们在询问9号点时，再一次访问了不存在的3号点的A这个儿子，而我们又会继续访问3号点的next所指的结点的A这个儿子，也就是说3号点的A这个儿子在整个操作中完全没有作用但是我们还会重复访问，所以我们就直接把3号点的A儿子直接定义为2号点，也就是next[3]：1的A儿子。这样我们在询问8号点的时候就可以直接将next[9]赋值为9的父结点的next结点的A这个儿子，也就是2号点。这样我们就是实现了O(n)的复杂度来建立next数组。（刚刚接触可能不是很理解，自己多画图模拟就明白了）
建立起next数组后，我们就可以直接让主串在trie树上跑，然后就可以愉快的dp了。
void trie(char *s)
{
int len=strlen(s),u=;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
if(!tree[u][c])
{
tree[u][c]=++tot;
}
u=tree[u][c];
}
bo[u]++;//记录每个模式串结尾的位置
}
建立trie树
void bfs()
{
for(int i=;i<=;i++)
tree[][i]=;//把0的所有出边都设为1
next[]=;q.push();//把1的next记为0，1号点入队
while(q.size())
{
int u=q.front();
q.pop();
for(int i=;i<=;i++)
{
if(!tree[u][i])
tree[u][i]=tree[next[u]][i];//这里就是上文所述的优化 如果u没有i这个儿子，
//那就把next[u]的i这个儿子当做u的i这个儿子
else
{
q.push(tree[u][i]);
int v=next[u];
next[tree[u][i]]=tree[v][i];
}
}
}
}
求next数组
void find(char *s)
{
int u=,len=strlen(s),k;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
u=tree[u][c];
}
}
主串匹配
接下来是一道模板题：
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#define maxn 1000005
using namespace std; inline int read()
{
int x=,res=;
char c=getchar();
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return res*x;
} int n,tot=,ans;
char a[maxn];
int tree[maxn][],next[maxn],bo[maxn];
queue<int>q; void trie(char *s)
{
int len=strlen(s),u=;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
if(!tree[u][c])
{
tree[u][c]=++tot;
}
u=tree[u][c];
}
bo[u]++;
} void bfs()
{
for(int i=;i<=;i++)
tree[][i]=;
next[]=;q.push();
while(q.size())
{
int u=q.front();
q.pop();
for(int i=;i<=;i++)
{
if(!tree[u][i])
tree[u][i]=tree[next[u]][i];
else
{
q.push(tree[u][i]);
int v=next[u];
next[tree[u][i]]=tree[v][i];
}
}
}
} void find(char *s)
{
int u=,len=strlen(s),k;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
k=tree[u][c];
while(k>&&bo[k]!=-)
{
ans+=bo[k];
bo[k]=-;
k=next[k];
}
u=tree[u][c];
}
} int main()
{
n=read();
for(int i=;i<=n;i++)
{
scanf("%s",a);
trie(a);
}
bfs();
scanf("%s",a);
find(a);
cout<<ans;
return ;
}
这还是一道模板题:
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#define maxn 1000005
using namespace std; struct tr
{
int next;
int vis[];
int end;
int num;
}tree[]; inline int read()
{
int x=,res=;
char c=getchar();
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return res*x;
} int n,tot,ans;
char b[][];
char a[maxn];
int f[];
queue<int>q; void trie(char *s,int num)
{
int len=strlen(s),u=;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
if(!tree[u].vis[c])
{
tree[u].vis[c]=++tot;
}
u=tree[u].vis[c];
}
tree[u].num=num;
} void bfs()
{
for(int i=;i<=;i++)
tree[].vis[i]=;
tree[].next=;q.push();
while(q.size())
{
int u=q.front();
q.pop();
for(int i=;i<=;i++)
{
if(!tree[u].vis[i])
tree[u].vis[i]=tree[tree[u].next].vis[i];
else
{
q.push(tree[u].vis[i]);
int v=tree[u].next;
tree[tree[u].vis[i]].next=tree[v].vis[i];
}
}
}
} void find(char *s)
{
int len=strlen(s),u=,k;
for(int i=;i<len;i++)
{
int c=s[i]-'a';
k=tree[u].vis[c];
while(k>)
{
f[tree[k].num]++;
k=tree[k].next;
}
u=tree[u].vis[c];
}
} int main()
{
while()
{
n=read();
if(n==) break;
memset(tree,,sizeof(tree));
memset(f,,sizeof(f));
tot=;ans=;
for(int i=;i<=n;i++)
{
scanf("%s",b[i]);
trie(b[i],i);
}
bfs();
scanf("%s",a);
find(a);
for(int i=;i<=n;i++)
{
ans=max(ans,f[i]);
}
cout<<ans<<endl;
for(int i=;i<=n;i++)
{
if(f[i]==ans)
printf("%s\n",b[i]);
}
}
return ;
}
最新文章
- Jquery EasyUI 开发实录
- js随机生成颜色代码
- 用js加密你的重要信息
- Android基础开发文档汇总
- 内核函数KiFastCallEntry
- [DFNews] EIFT更新至1.2，支持iPhone4s及iPhone5物理获取
- 利用 cos 组件实现jsp中上传附件
- 实习小记-python中不可哈希对象设置为可哈希对象
- PHP中的抽象类和接口
- List GetEnumerator
- 【C#学习笔记】窗口隐藏、最小化、最大化、正常化
- Ext.Net学习笔记03：Ext.Net MessageBus用法
- Undefined symbols for architecture x86_64:
- Chinese Rings hdu 2842 矩阵快速幂
- C#winform程序安装在默认路径提示权限不足的问题
- Linux socket 类封装 （面向对象方法）
- linq中如何在join中指定多个条件
- Go Socket实现简单的HttpServer
- SharePoint列表模板（.stp）
- MySQL（六）