在线视频网站开发,wordpress自动提交,中企动力官网 网站,做农业网站怎么赚钱题意#xff1a;
给定 n个长度不超过 50的由小写英文字母组成的单词准备查询#xff0c;以及一篇文章#xff0c;问#xff1a;文中出现了多少个待查询的单词。多组数据。
题目#xff1a;
In the modern time, Search engine came into the life of everybody like Go…题意
给定 n个长度不超过 50的由小写英文字母组成的单词准备查询以及一篇文章问文中出现了多少个待查询的单词。多组数据。
题目
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc. Wiskey also wants to bring this feature to his image retrieval system. Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched. To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match. Input First line will contain one integer means how many cases will follow by. Each case will contain two integers N means the number of keywords and N keywords follow. (N 10000) Each keyword will only contains characters ‘a’-‘z’, and the length will be not longer than 50. The last line is the description, and the length will be not longer than 1000000. Output Print how many keywords are contained in the description. Sample Input 1 5 she he say shr her yasherhs Sample Output 3
分析
此题为AC自动机模板匹配多模式串问题。单模式串匹配用KMP算法那么多模式串匹配不可能一个一个字符串建立失配数组复杂度太高0(m*n),所以对多模式串建成一个trie树再建立失配数组复杂度为o(nn\sqrt{n}n)。AC自动机详细分析见代码后。
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int N5e510;
int ans,tot,dp[N],ch[N][30],bo[N],que[N];
void makes(char *s)/**将所有模式串构建成一颗tire树*/
{int u1,lenstrlen(s);for(int i0; ilen; i){int cs[i]-a;if(!ch[u][c])ch[u][c]tot;uch[u][c];}bo[u];return ;
}
void bfs()/**通过BFS构建dp(失配)数组*/
{for(int i0; i26; i)ch[0][i]1;/**为了方便将0的所有转移边都设为根节点1*/que[1]1,dp[1]0;/**若在根节点失配则无法匹配字符*/for(int x1,y1; xy; x){int uque[x];for(int i0; i25; i){if(!ch[u][i])/**如果不存在u的转移边i时失配KMP*/ch[u][i]ch[dp[u]][i];///优化else{que[y]ch[u][i];/**若有这个儿子则将其加入队列中*/dp[ch[u][i]]ch[dp[u]][i];}}}
}
void find(char *s)
{int u1,lenstrlen(s),c,k;for(int i0; ilen; i){cs[i]-a;kch[u][c];while(k1){ansbo[k];bo[k]0;kdp[k];}uch[u][c];}return ;
}
int main()
{int t,n;char s[N1];scanf(%d,t);while(t--){ans0,tot1;memset(bo,0,sizeof(bo));memset(ch,0,sizeof(ch));scanf(%d,n);while(n--){scanf(%s,s);makes(s);}bfs();scanf(%s,s);find(s);printf(%d\n,ans);}return 0;
}AC自动机详细分解
ac自动机很神奇在于这个算法中失配指针的妙处好比kmp算法中的next数组说它高深是因为这个不是一般的算法而是建立在两个普通算法的基础之上而这两个算法就是kmp与字典树。ac自动机其实就是一种多模匹配算法那么你可能会问什么叫做多模匹配算法。下面是我对多模匹配的理解与多模与之对于的是单模单模就是给你一个单词然后给你一个字符串问你这个单词是否在这个字符串中出现过匹配这个问题可以用kmp算法在比较高效的效率上完成这个任务。那么现在我们换个问题给你很多个单词然后给你一段字符串问你有多少个单词在这个字符串中出现过当然我们暴力做用每一个单词对字符串做kmp,这样虽然理论上可行但是时间复杂度非常之高。
建立tire树(就是tire树模板)这个简单
void makes(char *s)/**将所有模式串构建成一颗tire树*/
{int u1,lenstrlen(s);for(int i0; ilen; i){int cs[i]-a;if(!ch[u][c])ch[u][c]tot;uch[u][c];}bo[u];return ;
}建立后此时多模式串为一个字典树将存在公共前缀的字符串“合并”可以用一个数组每个新点插入tot表示树上所有点。
建一个树的图 建立该字典树的失配数组(bfs队列KMP前缀数组重点
void bfs()/**通过BFS构建dp(失配)数组*/
{for(int i0; i26; i)ch[0][i]1;/**为了方便将0的所有转移边都设为根节点1*/que[1]1,dp[1]0;/**若在根节点失配则无法匹配字符*/for(int x1,y1; xy; x){int uque[x];for(int i0; i25; i){if(!ch[u][i])/**如果不存在u的转移边i时失配KMP*/ch[u][i]ch[dp[u]][i];///优化else{que[y]ch[u][i];/**若有这个儿子则将其加入队列中*/dp[ch[u][i]]ch[dp[u]][i];}}}
}首先建立的是一个tire树一个结点上可能连多个节点所以这里用BFS用进入队列的方式处理每一个点最后将tire树建立成一个可与给定串匹配的失配数组构建失配数组在代码中我写的是dp数组使当前字符失配时跳转到另一段最近匹配的位置【root开始每一个字符前缀都与当前已匹配字符段某一个后缀完全相同且长度最大的位置继续匹配】如同KMP算法一样AC自动机在匹配时如果当前字符串匹配失败那么利用失配指针进行跳转。由此可知如果跳转跳转后的串的前缀必为跳转前的模式串的后缀并且跳转的新位置的深度匹配字符个数一定小于跳之前的节点跳转后匹配字符数不可能大于跳转前否则无法保证跳转后的序列的前缀与跳转前的序列的后缀匹配。因为是一个字典树用ch数组表示是一个二维数组,ch[u][c],由于字典树c就为当前点totu为上一个点ch[u][c]就为当前点是否为树上的第几个点。 dp[ch[u][i]]等同于dp[i] 由tire树ch[u][c]tot(将字典树上的某一个链看做需要匹配的字符串) ch[dp[u]][i]等同于j(上次匹配位置的tot)) ;显然我们在构建失配数组的时候都是从当前节点的父节点的失配数组出发由于Trie树将所有单词中相同前缀压缩在了一起所以所有失配数组都不可能平级跳转到达另一个与自己深度相同的节点因为如果平级跳转很显然跳转所到达的那个节点肯定不是当前匹配到的字符串的后缀的一部分否则那两个节点会合为一个所以跳转只能到达比当前深度小的节点又是由当前节点ch[u][c]tot 父节点u 开始的跳转所以这样就可以保证从root到所跳转到位置的那一段字符串长度小于当前匹配到的字符串长度。另一方面我们可以类比KMP求NEXT数组时求最大匹配数量的思想那种思想在AC自动机中的体现就是当构建失配数组时不断地回到之前的跳转位置然后判断跳转位置的下一个字符是否包含当前字符如果是就将失配数组与那个跳转位置连接如果跳转位置指向tire树上的空点就说明当前匹配的字符在当前深度之前没有出现过无法与任何跳转位置匹配而若是找到了第一个跳转位置的下一个字符包含当前字符的的跳转位置则必然取到了最大的长度这是因为其余的当前正在匹配的字符必然在第一个跳转位置的下一个字符包含当前字符的的跳转位置深度之上而那样的跳转位置就算可以也不会是最大的最后一个字符的深度比当前找到的第一个可行的跳转位置的最后一个字符的深度小串必然更短一些。 if(!ch[u][i])/**如果不存在u的转移边i时失配KMP*/ch[u][i]ch[dp[u]][i];///优化(即找到后缀完全相同且长度最大的位置)如图
查询操作与字符串匹配)
void find(char *s)
{int u1,lenstrlen(s),c,k;for(int i0; ilen; i){cs[i]-a;kch[u][c];while(k1){ansbo[k];bo[k]0;kdp[k];}uch[u][c];}return ;
}如果节点匹配就一直进行下去每次都加每个节点的bo[u]并初始化为0但只有代表单词结尾的字符bo[u]才是1其他的为0.所以才有 while(k1){ansbo[k];bo[k]0;kdp[k];}例如在查询过程中匹配字符为abcdef,若有一个模式串为bc那么因为KMP只扫过前缀就会忽略导致结果错误所以每次让某匹配点失配看匹配串的后缀和之前匹配的前缀是否存在一模式串bo[u]!0到空点结束.
该查询默认一直匹配因为在构造失配数组时进行了优化,见下代码 if(!ch[u][i])/**如果不存在u的转移边i时失配KMP*/ch[u][i]ch[dp[u]][i];///优化(即找到后缀完全相同且长度最大的位置)导致一旦失配就会有点进行补充前面构造失配数组做的优化操作。 直到需要查询的串走完。 (总的来说算法比较神奇但是可以直接套KMP模板简单来说失配数组的作用就是将主串某一位之前的所有可以与模式串匹配的单词快速在Trie树中找出。)
俗话说言多必失更不要说我还是一个蒟蒻 QAQ 这么长的理解一定有地方有些小失误欢迎大犇来指正orz。
