每一组数据包含一个长度为 m 的字符串 S。现在有一个空串 T，每一次在字符集内随机一个字符加入到 T 的末尾，当 S 是 T 的子串时停止。求停止时 T 的期望长度。
做法简述
思路太清奇了，我也不知道怎么描述这个思路。这篇题解只能做到“尽量讲清楚这个做法”吧。
需要用到：生成函数基本知识（包括求导等）、KMP。
概率生成函数的性质
首先让我们认识一个叫概率生成函数的东西：f(x)=\sum_{i=0}^{+\infty} \mathrm{P}(X=i)x^i，也就是 i 次项的系数是随机变量 X 等于 i 的概率。
这个东西有什么用呢？这道题着重用到它的两个性质。
我们要求的是期望，和这个概率生成函数有什么关系呢？想一想，上面的式子想出现期望，是不是需要在 \mathrm{P}(X=i) 上乘一个 i 呀？如何让这个 i 出现呢？求导啊。于是这个式子也就可以理解了：f'(x)=\sum_{i=1}^{+\infty}i\mathrm{P}(X=i)x^{i-1}。为了全部加起来，我们令 x=1，得到 f'(1)=\sum_{i=1}^{+\infty}i\mathrm{P}(X=i)=\mathrm{E}(X)。
什么叫“无条件”呢？就是随机这 m 个字符的过程中，有可能还没随机够 m 个，就已经出现 S 了。这种情况下我们强迫它一定要随机够 m 个。
相当于，h_i 表示的是这一个事件 A 的发生概率：
有一天你开始随机，随机了 i 个字符还没有随机出 S，你失去了耐心，说：“无论如何，再给我随机 m 个！”然后 m 个过后，你发现这 m 个字符恰好是 S！
解释了 h_i 的含义，如何计算 h_i 呢？
第一种方法比较简单。上面两个条件是彼此独立的，因此可以把“随机了 i 个字符都没有停止”和“无条件随机 m 个字符，恰好得到 S”的概率乘起来，也就是 h_i=g_i n^{-m}（注意，n 是字符集大小）。
第二种方法比较神奇，运用了分类讨论（或者说全概率公式）。
我们注意到，如果事件 A 发生，那么第一次出现 S 的时刻（也就是上面定义的 Y）一定满足 i<Y\le i+m（i+m 的时候一定已经出现了 S，所以 Y\le i+m）。因此我们讨论 Y 的每一个取值。
假设 Y=y，那么这个前提的概率就是 f_y。下面只需要求出在这个前提下事件 A 发生的概率，再把这个概率乘以 f_y 并全部加起来（根据全概率公式）就好了。
这个前提下事件 A 发生的概率是多少呢？
记 t=y-i\ (0<t\le m)。那么 y 时刻（也就是第一次出现 S 的时候），已经随机了这 m 个字符中的 t 个了。如果要发生事件 A，就得满足，这 t 个字符恰好是 S 的前 t 个（条件 a），并且后面再随机的 m-t 个字符恰好是 S 的剩余 m-t 个字符（条件 b）。
然而，由于 y 时刻恰好出现了 S，那也就意味着这 t 个新的字符也恰好是 S 的那个长度为 t 的后缀。也就是说，这 t 个字符是确定的。条件 a 能够满足，就等价于，这个后缀必须同时也是 S 的前缀——想到了什么？这就是说，这个后缀必须是 S 的 border！（注意，这里和 border 的一些定义有所不同的是，我们认为 S 本身也是 S 的一个 border。也就是说，只要一个串既是 S 的前缀，又是 S 的后缀，那么我们就把这个串叫做 S 的 border。）总结一下，条件 a 等价于这个长度为 t 的后缀是 S 的 border。
条件 b 是概率性的，剩下来的字符和前面的是独立的，因此这 m-t 个字符满足要求的概率就是 n^{-(m-t)}=n^{t-m}。
因此，Y=y,\ t=y-i 的前提下，同时满足条件 a 和 b 的概率（也就是事件 A 发生的概率）是 \mathrm{isborder}(t)\times n^{t-m}，其中 \mathrm{isborder}(t) 的取值为 1 或 0，表示长度为 t 的后缀是否是 S 的一个 border。
根据全概率公式，把所有可能情况的概率加起来，事件 A 发生的概率就是 \sum_{t=1}^{m}f_{i+t}n^{t-m}\mathrm{isborder}(t)（注意 t=y-i,\ y=i+t，因此 f_y=f_{i+t}）。
上面的式子换一种写法就是 h_i=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}，这个求和号的意思是对所有 S 的 border 求和，求和的时候把这个 border 的长度带入到被求和式当中的 t 中。
整理一下，我们用两种方法计算 h_i，分别得到了 h_i=g_i n^{-m} 和 h_i=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}，因此 g_i n^{-m}=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}。这又是一个关于 g 和 f 的式子！
上面这个式子两边乘以 n^m 得到 g_i=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t}，看上去好多了。
因此，上面的式子整理成生成函数就是 x^mg(x)=\sum_{S\text{的} t \text{长border}} x^{m-t}f(x)n^{t}。
得到答案
上面的式子看上去还是很丑是吧？别忘了我们只要求出 g(1) 就是答案了。
将 x=1 代入上面的式子得到 g(1)=\sum_{S\text{的} t \text{长border}} f(1)n^{t}，又根据概率生成函数的性质，f(1)=1，因此 g(1)=\sum_{S\text{的} t \text{长border}} n^{t}。太神奇了！
根据这个式子，答案就是 \sum_{S\text{的} t \text{长border}} n^{t}。因此我们只需要找出 S 的所有 border，把 n^t 累加到答案里就可以了。这个可以用 KMP，或者由于我们可以枚举 border 长度，用哈希判断前后缀是否相等。
时间复杂度 O(m)。
特别注意：如果用 KMP 求，一定记得这道题中 S 本身也算 S 的一个 border！
代码实现
式子推完了，代码应该非常容易写。提供我用 KMP 写的代码。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x) \
freopen(x".in","r",stdin); \
freopen(x".out","w",stdout);
#define MAXN 100005
#define MOD 10000
#define N 100000
#define MD(x) (((x)>=MOD)?((x)-=MOD):(0))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读，实现略去
void ayano(io_t x,char spliter='\n'); //快写，本题没用到
int spw[MAXN]; // 字符集大小（题目中的 n）的幂的预处理
int knxt[MAXN]; // KMP 的 next 数组
int arr[MAXN]; // 字符串
int main(void){
int s,testdatas; //s 表示题目中的 n
s=seto()%MOD,testdatas=seto();
spw[0]=1;
for (int i=1;i<=N;i++)
spw[i]=spw[i-1]*s%MOD;
while (testdatas--){
int n=seto(); //表示题目中的 m
// KMP 计算 next
knxt[0]=-1;
for (int i=1;i<=n;i++){
int cur=seto();
arr[i]=cur;
int tnxt=knxt[i-1];
while (tnxt>=0){
if (arr[tnxt+1]==cur)
break;
tnxt=knxt[tnxt];
}
knxt[i]=tnxt+1;
}
int t=n;
int ans=0;
// 在 next 数组上跳，枚举每一个 border
while (t)
ans+=spw[t],MD(ans),t=knxt[t];
//输出答案
putchar(ans/1000+'0'),putchar(ans/100%10+'0'),
putchar(ans/10%10+'0'),putchar(ans%10+'0'),putchar('\n');
}
return 0;
}