怎么建立一个网站,天津网站建设服务公司,网上免费注册网站,wordpress 3.2 下载题目链接 \(Description\) 给定n个模式串#xff0c;多次询问一个串在多少个模式串中出现过。(字符集为26个小写字母) \(Solution\) 对每个询问串进行匹配最终会达到一个节点#xff0c;我们需要得到这个节点所代表的子串出现在多少个模式串中。 建立广义后缀自动机。每次插入… 题目链接 \(Description\) 给定n个模式串多次询问一个串在多少个模式串中出现过。(字符集为26个小写字母) \(Solution\) 对每个询问串进行匹配最终会达到一个节点我们需要得到这个节点所代表的子串出现在多少个模式串中。 建立广义后缀自动机。每次插入一个串从root开始对于SAM上每个节点维护cnt和bef分别表示该节点代表的串出现在几个模式串中 和 该节点最近被哪个模式串更新过cnt。 对于bef[i]!now的节点cnt[i],bef[i]now当模式串now下次匹配到当前节点时则不再更新。 另外如果匹配了当前节点i那么一定会匹配上fa[i],fa[fa[i]]...如果它们的bef[]!now则都更新一遍。直到有个节点p满足bef[p]now那么就不需要再向上更新了再往上已经更新过了。(这个在insert后用np更新就可以啊) 这个暴力跳的复杂度可能是\(O(n\sqrt n)\)的但是很难卡满广义SAM上一个点暴力跳fa的次数是\(O(\sqrt n)\)的具体见这里。 有一种离线DFS序树状数组的做法可以做到\(\log n\)。注意广义SAM应该要像这题那么建 但事实上这题还有个剪枝bef[np]now广义SAM上情况比较复杂我也不知道真正的复杂度是啥。。 注意新建nq时 bef[nq],cnt[nq]也要复制(...[q])。 //24612kb 76ms
#include cstdio
#include cstring
#include algorithm
#define gc() getchar()
const int N2e55;struct Suffix_Automaton
{int las,tot,fa[N],son[N][26],len[N],cnt[N],bef[N];char s[360005];void Init(){lastot1;}void Insert(int now,int c){int plas,nptot; len[lasnp]len[p]1;for(; p!son[p][c]; pfa[p]) son[p][c]np;if(!p) fa[np]1;else{int qson[p][c];if(len[q]len[p]1) fa[np]q;else{int nqtot;len[nq]len[p]1, bef[nq]bef[q], cnt[nq]cnt[q];//!memcpy(son[nq],son[q],sizeof son[q]);fa[nq]fa[q], fa[q]fa[np]nq;for(; son[p][c]q; pfa[p]) son[p][c]nq;}}for(; bef[np]!nownp; npfa[np])cnt[np], bef[np]now;}void Build(int now){las1, scanf(%s,s);for(int i0,lstrlen(s); il; i)Insert(now,s[i]-a);}void Query(){int p1; scanf(%s,s);for(int i0,lstrlen(s); ilp; i)pson[p][s[i]-a];printf(%d\n,cnt[p]);}
}sam;int main()
{int n,Q; scanf(%d%d,n,Q); sam.Init();for(int i1; in; i) sam.Build(i);while(Q--) sam.Query();return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/9240586.html
