首页 > 代码库 > 【bzoj2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
【bzoj2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
题目描述
Oimaster and sevenk love each other.
But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman‘s nature, sevenk felt angry and began to check oimaster‘s online talk with ChuYuXun. Oimaster talked with ChuYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this, "how many strings in oimaster‘s online talk contain this string as their substrings?"输入
There are two integers in the first line, the number of strings n and the number of questions q.And n lines follow, each of them is a string describing oimaster‘s online talk. And q lines follow, each of them is a question.n<=10000, q<=60000 the total length of n strings<=100000, the total length of q question strings<=360000输出
For each question, output the answer in one line.样例输入
3 3
abcabcabc
aaa
aafe
abc
a
ca
样例输出
1
3
1
题目大意
给出n个字符串和q个询问，每次询问给定的字符串在多少个字符串中出现过（为多少个字符串的子串）。
题解
这种单字符串为多字符串的子串的问题，当然要用广义后缀自动机
对于后缀自动机上的每个节点，我们再开两个数组vis和si，记录一下它最后一个属于的字符串是什么，以及它属于多少个字符串。
那么当插入一个字符之后，应该更新它的vis和si信息，如果vis不等于当前字符串，则将vis更新，并将si++。由于它的parent树上的祖先节点与它有着相同信息，应该一起更新，即不断向上寻找fa，直到不存在fa或已经被更新过为止。
同时，当插入过程中新建节点nq时，由于它是用来代替q的，所以应该把q的vis、si赋给nq。
大量实践证明，这样做的时间复杂度是$O(n)$的（其实我也不太会证）
最后对于每个询问串，在后缀自动机中不断查找，最后节点的si即为答案。
#include <cstdio>#include <cstring>#include <algorithm>#define N 400010using namespace std;int next[N][26] , fa[N] , dis[N] , vis[N] , si[N] , last , tot = 1;char str[N];void insert(int c , int t){ int p = last , np = last = ++tot; dis[np] = dis[p] + 1; while(p && !next[p][c]) next[p][c] = np , p = fa[p]; if(!p) fa[np] = 1; else { int q = next[p][c]; if(dis[q] == dis[p] + 1) fa[np] = q; else { int nq = ++tot; memcpy(next[nq] , next[q] , sizeof(next[q])) , si[nq] = si[q] , vis[nq] = vis[q] , dis[nq] = dis[p] + 1 , fa[nq] = fa[q] , fa[np] = fa[q] = nq; while(p && next[p][c] == q) next[p][c] = nq , p = fa[p]; } } for(p = np ; p && vis[p] != t ; p = fa[p]) vis[p] = t , si[p] ++ ;}int main(){ int n , m , i , j , l; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) { scanf("%s" , str) , l = strlen(str); for(j = 0 , last = 1 ; j < l ; j ++ ) insert(str[j] - ‘a‘ , i); } while(m -- ) { scanf("%s" , str) , l = strlen(str); for(i = 0 , j = 1 ; i < l ; i ++ ) j = next[j][str[i] - ‘a‘]; printf("%d\n" , si[j]); } return 0;}
【bzoj2780】[Spoj]8093 Sevenk Love Oimaster 广义后缀自动机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。