UC知道C编程的问题
来源：百度知道 编辑：UC知道 时间：2024/05/28 16:58:51
Problem G: Generator
We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as a specific pattern occurs in the random string.
Your task is to predict the expected length of the generated string.
Input Description
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
Each test case consists of a single integer N (1 <= N <= 26) which is the number of letters used, and a pattern, which is a non-empty string consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 12.
We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as a specific pattern occurs in the random string.
Your task is to predict the expected length of the generated string.
Input Description
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
Each test case consists of a single integer N (1 <= N <= 26) which is the number of letters used, and a pattern, which is a non-empty string consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 12.
这是ZJU Monthly么？
我觉得期望步数不一定是整数啊，为什么输出没有提到这个问题。
算法大致如下：
1.建立以“当前生成串的后缀匹配模板串前缀的长度”为状态的自动机。
2.构建出自动机的转移规则，也就是说在某个状态下若生成某个特定的字符会转移到哪个状态，由于字符串长度很小，所以可以直接暴力枚举。
3.设到达自动机每个状态的期望步数为Xi.
4.列出L(L为模板串长度)元一次线性方程组：Xi = sigma(1/L*Xp),其中Xp为所有可转移到Xi状态的其它（包括自身）状态。
5.解方程组，即可得到XL的期望步数，也就是答案。
另外，由于题目要求的输出精度有相当的规模，建议使用Java语言编写，使用Big Decimal类型。
没怎么看懂。
你可以把你写的程序发上来，我帮你修改一下的。
就算我会做,也没心情看全英文的
没有看懂