怎么查看网站是哪家公司做的,在建设部网站上的举报,网络广告创意策划,如何制造公司网站所谓广义SAM#xff0c;就是更广泛意义下的SAM #xff08;逃#xff09;
前言
感觉字符串的理解难度的巅峰还是在SAM#xff0c;广义SAM只是在套一些特判罢了#xff0c;并不是太难理解。 可以解决多字符串的子串问题#xff0c;几乎就是把SAM能做的东西从单串变成了多… 所谓广义SAM就是更广泛意义下的SAM 逃
前言
感觉字符串的理解难度的巅峰还是在SAM广义SAM只是在套一些特判罢了并不是太难理解。 可以解决多字符串的子串问题几乎就是把SAM能做的东西从单串变成了多串。
解析
在线做法
有一个很流行的盗版做法是每次加入新串时把 lstlstlst 重新赋值为 111然后就和正常SAM一样做。 但这会出现一些问题就是当 translst,ctrans_{lst,c}translst,c 存在时我们会加入空节点。 这里的空节点的具体含义是指其 minlenmaxlenminlenmaxlenminlenmaxlen从而使得该结点代表的等价类没有任何字符串。 这个时候我们进行特判即可后面还是按照正常SAM做。
struct SAM{int tr[N][26],fa[N],len[N],tot,lst;SAM(){totlst1;}inline int ins(int c,int p){c-a;if(tr[p][c]){int qtr[p][c];if(len[q]len[p]1) return q;else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];for(int i0;i26;i) tr[nq][i]tr[q][i];fa[q]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;return nq;}}else{int curtot;len[cur]len[p]1;for(;p!tr[p][c];pfa[p]) tr[p][c]cur;if(!tr[p][c]) fa[cur]1;else{int qtr[p][c];if(len[q]len[p]1) fa[cur]q;else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];for(int i0;i26;i) tr[nq][i]tr[q][i];fa[q]fa[cur]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;}}return cur;}}inline void addstring(char *s){int nstrlen(s1),lst1;for(int i1;in;i) lstins(s[i],lst);return;}
}sam;然而这个做法对一棵 trietrietrie 树建SAM的时候复杂度是 O(G(T))O(G(T))O(G(T)) 的G(T)G(T)G(T) 表示所有叶子的深度和这在许多时候会被卡成 O(n2)O(n^2)O(n2)因此我们需要寻找另一种做法。
离线做法
这个方法对于 trietrietrie 树建SAM的复杂度是优秀的 O(T)O(T)O(T)。 考虑bfs从而使得深度单调不降。 每次取出队首以它父亲在SAM上对应的结点 作为 lstlstlst 进行插入即可。由于 trietrietrie 树本身的性质此时必然有 translst,cNULLtrans_{lst,c}NULLtranslst,cNULL因此直接按照正常的SAM写即可。
struct SAM{int tr[N][26],pos[N],len[N],fa[N],tot;SAM(){tot1;}inline int ins(int c,int p){int curtot;len[cur]len[p]1;for(;p!tr[p][c];pfa[p]) tr[p][c]cur;if(!tr[p][c]) fa[cur]1;else{int qtr[p][c];if(len[q]len[p]1) fa[cur]q;else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];for(int i0;i26;i) tr[nq][i]tr[q][i];fa[q]fa[cur]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;}}return cur;}int q[N],st,ed;void build(){q[sted1]1;pos[1]1;while(sted){int nowq[st];//pos[now]ins(trie.col[now],pos[trie.fa[now]]);for(int i0;i26;i){int totrie.tr[now][i];if(to){q[ed]to;pos[to]ins(trie.col[to],pos[now]);}}}return;}
}sam;
