怎么做网站推广的论文,网站模板没有html文件下载,广州建设官方网站,南昌建设银行网站Aho-Corasick automaton是什么#xff1f; 要学会AC自动机#xff0c;我们必须知道什么是Trie#xff0c;也就是字典树。Trie树#xff0c;又称单词查找树或键树#xff0c;是一种树形结构#xff0c;是一种哈希树的变种。典型应用是用于统计和排序大量的字符串#xff…Aho-Corasick automaton是什么 要学会AC自动机我们必须知道什么是Trie也就是字典树。Trie树又称单词查找树或键树是一种树形结构是一种哈希树的变种。典型应用是用于统计和排序大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。 首先我们要知道trie而且要知道KMP这样就可以学AC自动机了! 其实AC自动机就是trie和KMP的结合体。主要构建trie后使用KMP的主导思想构建fail边每次匹配与KMP相似。 下面我们看看如何构造fail边。 fail边就是类似KMP中的next数组在失配的时候能够指向的地方。 这就是一颗trie树那么我们应该怎么去连fail边呢 首先我们知道root的fail边是连向自己的而且所有与root直接相连的点fail都指向root。 然后每个点看看自己父亲的fail边指向的位置的点是否有一个与它长的一样的儿子如果有那么连上否则继续找fail边直到root为止(注意这个过程我们用bfs实现)。所以最终连完的fail边就是这样 这样我们只需要每一位去匹配就好了。 有人问怎么匹配 举个栗子 用上面的图 假设原串是ahershe这棵trie上有his,her,he,she。 我们从root开始先查找root点有没有当前字母的儿子a有那么指针x指到h点上这样一直匹配如果没有那么就直接跳到当前点的fail边上这样保证前面匹配的全都是相同的直到有这样的儿子或者已经到了root并且没有这样的儿子为止。 注意每跳一个点就必须从当前点遍历一遍它的fail边直到root的边集就是说沿着fail边跳一直到root为止这是为了避免当前点没有被标记但是在它fail边到达root的路径上有被标记的点。 Exanple 【GDOI2013模拟4】贴瓷砖 Description A镇的主街是由N个小写字母构成镇长准备在上面贴瓷砖瓷砖一共有M种第i种上面有Li个小写字母瓷砖不能旋转也不能被分割开来瓷砖只能贴在跟它身上的字母完全一样的地方允许瓷砖重叠并且同一种瓷砖的数量是无穷的。 问街道有多少字母(地方)不能被瓷砖覆盖。 Input 第一行输入街道长度N(1N300,000)。 第二行输入N个英文小写字母描述街道的情况。 第三行输入M(1M5000)表示瓷砖的种类。 接下来M行每行描述一种瓷砖长度为Li(1Li5000)全部由小写字母构成。 Output 输出有多少个地方不能被瓷砖覆盖。 Sample Input 输入1 6 abcbab 2 cb cbab 输入2 4 abab 2 bac baba 输入3 6 abcabc 2 abca cab Sample Output 输出1 2 输出2 4 输出3 1 Data Constraint N(1N300,000) Solution 我们把原字符串每一位都进行匹配然后首先预处理出trie中每一个点对应所有fail边中最大的长度然后匹配的时候记录下每一位中能够覆盖到的最大长度最后用线段树维护(当然你可以直接用差分约束)。 Code #includecstdio
#includeiostream
#includecstring
#define mo 1000010
using namespace std;
struct Moon{int fail,num,maxl;}point[4000010];
int son[4000010][27];
int lengt_max[300010],length[300010];
char s[300010],ch[300010];
int len,n,root,sz;
int d[mo];
int f[300010*4],tag[300010*4];
void make_trie(char s1[300010],int len1,int t,int x,int id)
{if(tlen1) {point[x].numid;point[x].maxllength[id];return;} if(!son[x][s1[t]-96]){son[x][s1[t]-96]sz;son[x][0];make_trie(s1,len1,t1,sz,id); }else make_trie(s1,len1,t1,son[x][s1[t]-96],id);
}
void build_fail()
{int i,x,k,head0,tail0;for (i1;i26tailson[root][0];i)if(son[root][i]) {d[tail]son[root][i];point[son[root][i]].failroot;}while(head!tail){headhead%mo1;xd[head];if(!son[x][0]) continue;for (i1;i26;i)if(son[x][i]){tailtail%mo1;d[tail]son[x][i];kpoint[x].fail;while(k!root){if(son[k][i]) break;kpoint[k].fail;if(kroot!son[k][i]) break;}if(son[k][i]) point[son[x][i]].failson[k][i];else point[son[x][i]].failroot;point[son[x][i]].maxlmax(point[son[x][i]].maxl,point[point[son[x][i]].fail].maxl);}}
}
void Check()
{int xroot,k;for (int i1;ilen;){if(son[x][s[i]-96]) {xson[x][s[i]-96]; lengt_max[i]max(lengt_max[i],point[x].maxl);i;} else xpoint[x].fail;if(xroot!son[x][s[i]-96]) i;}
}
void change(int v,int l,int r,int x,int y)
{if(lxry){tag[v]1;f[v]r-l1; return;}int mid(lr)/2;if(tag[v]){tag[v*2]1,f[v*2]mid-l1;tag[v*21]1,f[v*21]r-mid;tag[v]0;}if(ymid) change(v*2,l,mid,x,y);else if(xmid) change(v*21,mid1,r,x,y);else change(v*2,l,mid,x,mid),change(v*21,mid1,r,mid1,y);f[v]f[v*2]f[v*21];
}
int main()
{scanf(%d,len);scanf(%s,s1);scanf(%d,n);int i,j;rootszpoint[1].fail1;for (i1;in;i){scanf(%s,ch1);length[i]strlen(ch1);make_trie(ch,length[i],1,root,i);}build_fail();Check();for (i1;ilen;i) if(lengt_max[i]) change(1,1,len,i-lengt_max[i]1,i);printf(%d\n,len-f[1]);
} 转载于:https://www.cnblogs.com/Chandery/p/11332808.html
