题目链接：https://www.luogu.com.cn/problem/P4548
补了一下概率生成函数。
写的公式可能不规范请不要介意。
给出某个字符串(S)，你手中有个字符串(T)一开始为空。每次随机往(T)后加一个字符，问(S)成为(T)的子串的期望次数。
字符集大小为(c)。
正解是一条式子。可以做到(O(n))。
介绍下概率生成函数：(F(x)=sum_i P(i)x^i)，(P(i))表示某个要求的变量最终值为(i)的概率。
于是有两条性质：(F(1)=1)（即所有概率加起来），(F'(1)=E)。(E)表示期望，即(sum i P(i))。
回到这题。设(f_i)表示结束的时候长度为(i)的概率，(g_i)表示长度为(i)的时候还没有结束的概率。(F(x),G(x))分别为它们的生成函数。
显然有(F(x)+G(x)=xG(x)+1 (1))。
又根据意义可得(G(x)(frac{1}{c}x)^L=sum a_iF(x)(frac{1}{c}x)^{L-i}(2))。其中(a_i)表示(i)是否为(S)的(border)。意义：左式表示一个还不包含(S)的串后面硬塞了一个(S)的方案数；但这个时候可能会提前结束，右边那个就是结束了之后再多塞了(S_{L-i+1..L})。由于在右边(F(x))相当于钦定了第一个结束的位置，所以不会算重。
根据这两个式子乱搞：
对((1))求导得(F'(x)=(x-1)G'(x)+G(x))，代入(x=1)得(F'(1)=G(1))。
对((2))代入(x=1)得(G(1)=sum a_iF(1)c^i)。
两条式子结合前面给出的两条概率生成函数的性质，得到(E=sum a_ic^i)。