{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\n你的朋友是一名生物学家。他刚刚测序了一段DNA,并想知道不同基因在该DNA中的贡献。基因和DNA都可以用字母或字符串的序列表示。给定DNA的序列**D**和基因**G**;你的朋友使用以下方法计算贡献。\n\n1. 生成一个基因**G**的适当非空前缀列表**P**和另一个适当非空后缀列表**S**[1]。此外,让**L**是所有前缀和后缀的串的列表。所以如果**G \u003d ACCT**,那么**P \u003d A, AC, ACC**,**S \u003d T, CT, CCT**,**L \u003d AT, ACT, ACCT, ACT, ACCT, ACCCT, ACCT, ACCCT, ACCCCT**。如果**|G| \u003d n**,那么很明显**L**的大小是**(n - 1)\u003csup\u003e2\u003c/sup\u003e**。\n2. 对于**L**的每个元素,在**D**中计算它作为子串出现的次数。基因**G**在DNA**D**中的贡献是这些值的总和。例如,如果**D \u003d ACTACCTACCCCT**,则:\n\n\n\n| 基因 | 频率 |\n| --------- | --------- |\n| AT | 0 |\n| ACT | 1 |\n| ACCT | 1 |\n| ACT | 1 |\n| ACCT | 1 |\n| ACCCT | 0 |\n| ACCT | 1 |\n| ACCCT | 0 |\n| ACCCCT | 1 |\n| **总计** | **6** |\n\n\n\n由于这个过程非常繁琐,他希望能自动化这个过程。由于他不是程序员,他需要你的帮助。如果你能写一个程序,读取DNA和基因的序列,并计算基因在DNA中的贡献,他将非常感激。\n"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数**T(\u0026le; 20)**开头,表示测试用例的数量。\n\n每个测试用例包含两行。第一行包含一个字符串,表示DNA的序列,第二行包含另一个字符串,表示基因。每个字符串的长度小于**50000**,并且只包含**A,C,T**和**G**。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,按照上述描述,打印案例编号和贡献。"}},{"title":"示例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\nACTACCTACCCCT\nACCT\nAAA\nAAAA\nAAAA\nAAA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: 4\nCase 3: 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"MD","content":"1. 字符串**S**的适当前缀(后缀)是长度小于**|S|**的前缀(后缀)。这里**|S|**表示**S**的长度。\n2. 数据集非常庞大,请使用更快的I/O方法。"}}]}