很有趣的期望题目。可以使用概率意义求解，也可以使用概率生成函数 PGF 求解，还可以直接 DP 求解。
概率意义
很巧妙啊。
概率意义解法确实很巧妙。设字符集大小为 $c$。假设这里是一个赌场，每一个时刻都有一个赌徒。赌博方式是，赌徒在 $t$ 时刻用 $x$ 枚钱币赌下一秒出现 $y$，赌对了则返还 $cx$ 枚钱币。这显然是一个公平赌博游戏。赌徒最开始在下一秒赌出现 $a_1$，赌错了则立刻跑路，赌对了则用获得所有钱币，继续赌下秒出现 $a_2$，以此类推。直到最终出现出现了整个名字 $a$，此时赌场关闭。整个过程结束。
考虑结束前出现的整个名字 $a$。根据上述过程容易发现，只有 在这段字符串的 Border 对应的后缀（假设包含原串）出现赌徒会获得收益，并且设 Border 长度为 $x$，那么对应位置的赌徒获得的收益为 $c^x$。其余位置的赌徒收益均为 $0$。
此时关键来了，由于是公平赌博游戏，所以赌场的赚与赔是不受赌徒与赌场采用的策略影响的。意味着赌场期望收益为 $0$。又因为赌场向获得收益的赌徒支付了 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$，所以期望有 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$ 个赌徒才会出现赌场关闭的情况。所以得出答案就是 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$。
概率生成函数 PGF
这个也挺牛逼的。
我们介绍概率生成函数 PGF：
比较显然的一点是 $F(1)=1$。我们如何与期望建立联系？我们似乎需要在系数上再乘上一个 $i$。比较妙的是，我们考虑对 $F(x)$ 求导得到 $F’(x)$：
我们就得到了 $F’(1)=E(X)$。总结一下，我们得到 $F(1)=1,F’(1)=E(X)$。