题意：字符集 ，给定一个长为 的字符串 ，字符串 初始时为空，每次从 等概率取一个数加到 的末尾。若 在 中出现则停止，求 的期望长度。
多组数据，，，时限 。
设最终 的长度为 ，这是经典的 KMP
自动机上随机游走问题。
定义 ，有 ，天然有方程
考虑再找出一个方程。观察集合 ，在这些字符串中，
肯定出现了，但它们并不一定是"能被识别的串"，因为可能在加入 的半途就到达终止点，导致走过头。
例：， 尚未终止，但 过头了，无法识别。
对于 ， 一定能表示成
的形式，其中
，
是走过头了的那部分
的后缀。（易知这种表示是唯一的）
考虑逆映射，对于 和任意 ，都有对应的 使得
吗？答案是否定的。注意到
的末尾是 ：
这要求 （重合的灰色部分）。可以发现这是充分的，于是 记 ，这相当于判断 是否为 Border，容易 KMP 求出。
翻译为 PGF 得 其中 。
复杂度 。