题意：给出一个键盘，按键都是大写字母。给出一个目标单词和一个长度L。最大值或者最大长度都是100。现在随机按键盘，每个按键的概率相同。
敲击出一个长度为L的序列。求该序列中目标单词最多可能出现几次，期望出现几次。输出两者的差。
分析：概率题
先求最大次数。直接看该目标单词首尾最大重叠多长，暴力求解即可。然后通过除法运算求最多出现几次。
求期望涉及到一个Linearity of Expecation的知识，用中文形象的描述可以称之为“期望重组”。
期望重组
现有随机变量X，传统求X期望的方法是把X的每个取值乘以其概率再加和。
而现在我们要对X的每个取值进行重组。
例如，E(X)=sigma(xi*pi)。当X=xi时，我们把X看作是n个随机变量的和。pi是恰好和为xi时的概率。
这想当与是按照X的每种取值进行分类计算。
现在我们给出另外一种求法。
设这n个随机变量总共有M种不同的取值方法。
（如果这些随机变量相互独立，那么M=m1*m2*...*mn，mi表示第i个随机变量有多少种取值。）
我们对于每一个随机变量ai都把M种情况枚举一次，计算每种情况发生的概率乘以ai在该种情况下的取值，并加和。
最后把所有随机变量的加和再加和，就是我们要求的E(X)。
详细说明请google搜索linearity of expectation。
根据期望重组我们可以轻松求出单词出现的次数，我们先求出在总长度的每个位置出现目标单词的期望。当然出现次数只能是0或1。
再乘以可能出现位置的总数即可。
这其实相当于对每个可能出现单词的位置都枚举了整个长度L串的所有情况。
但因为对于一个位置，很多位的取值并不会影响该位置是否会出现目标单词，所以也不用进行分类直接把那些位的所有情况看成一个整体，概率为1。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define D(x) const int MAX_N = ;
const int MAX_KEY = ; int key_len, word_len, tot_len;
char keyboard[MAX_N], word[MAX_N];
int num[MAX_N]; void input()
{
scanf("%d%d%d", &key_len, &word_len, &tot_len);
scanf("%s%s", keyboard, word);
} bool ok(int a)
{
for (int i = a; i < word_len; i++)
if (word[i] != word[i - a])
return false;
return true;
} int get_max_time(int overlap)
{
for (int i = ; i < word_len; i++)
if (num[word[i] - 'A'] == )
return ;
if (tot_len < word_len)
return ;
return + (tot_len - word_len) / overlap;
} void work()
{
fill_n(num, , );
for (int i = ; i < key_len; i++)
num[keyboard[i] - 'A']++; int max_time = ;
int overlap = word_len;
for (int i = ; i < word_len; i++)
{
if (ok(i))
{
overlap = i;
break;
}
}
max_time = get_max_time(overlap); double ans = ;
for (int i = ; i < word_len; i++)
ans *= num[word[i] - 'A'] * 1.0 / key_len;
ans *= tot_len - word_len + ;
D(printf("%.3f\n", ans));
D(printf("%d\n", max_time));
printf("%.8f\n", max_time - ans);
} int main()
{
int t;
scanf("%d", &t);
int case_num = ;
while (t--)
{
case_num++;
printf("Case #%d: ", case_num);
input();
work();
}
return ;
}