「BZOJ 1921」「Ctsc2010」珠宝商
题意
给一棵 \(n\) 个点的树和长度为 \(m\) 的特征串,树的每个节点有一个字符。
求随机两个点形成有向路径上构成的串在特征串里出现次数的期望
仅含小写字母,\(n,m\le 5*10^4\)
给一棵 \(n\) 个点的树和长度为 \(m\) 的特征串,树的每个节点有一个字符。
求随机两个点形成有向路径上构成的串在特征串里出现次数的期望
仅含小写字母,\(n,m\le 5*10^4\)
第一篇算法相关
第一次自己想sam
给出一个长度为\(n\)的字符串\(s\)。
如果一个字符串序列\(t_1,\dotsc,t_k\),\(\forall1<i\le k\),\(t_i\)是\(t_{i-1}\)的一个子串,且长度严格小,那么称这个字符串序列是一个journey
。
一个journey
的长度是其中字符串的数量
求最长的journey
,满足存在字符串序列\(u_1,\dotsc,u_{k+1}\)(可以为空),使\(s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}\)。