{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle\u003e\n\u003c!--\n /* Font Definitions */\n @font-face\n\t{font-family:Mangal;\n\tpanose-1:2 4 5 3 5 2 3 3 2 2;}\n@font-face\n\t{font-family:\"Cambria Math\";\n\tpanose-1:2 4 5 3 5 4 6 3 2 4;}\n@font-face\n\t{font-family:Cambria;\n\tpanose-1:2 4 5 3 5 4 6 3 2 4;}\n@font-face\n\t{font-family:Calibri;\n\tpanose-1:2 15 5 2 2 2 4 3 2 4;}\n@font-face\n\t{font-family:Tahoma;\n\tpanose-1:2 11 6 4 3 5 4 4 2 4;}\n@font-face\n\t{font-family:Garamond;\n\tpanose-1:2 2 4 4 3 3 1 1 8 3;}\n@font-face\n\t{font-family:Verdana;\n\tpanose-1:2 11 6 4 3 5 4 4 2 4;}\n@font-face\n\t{font-family:\"Bernard MT Condensed\";\n\tpanose-1:2 5 8 6 6 9 5 2 4 4;}\n@font-face\n\t{font-family:\"Bookman Old Style\";\n\tpanose-1:2 5 6 4 5 5 5 2 2 4;}\n@font-face\n\t{font-family:\"Courier 10 Pitch\";}\n@font-face\n\t{font-family:\"DejaVu Sans\";}\n@font-face\n\t{font-family:\"\\@Courier 10 Pitch\";}\n@font-face\n\t{font-family:\"\\@DejaVu Sans\";}\n /* Style Definitions */\n p.MsoNormal, li.MsoNormal, div.MsoNormal\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:0in;\n\ttext-align:justify;\n\tline-height:115%;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\nh1\n\t{mso-style-link:\"Heading 1 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tline-height:115%;\n\tpage-break-after:avoid;\n\tfont-size:14.0pt;\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:green;}\nh2\n\t{mso-style-link:\"Heading 2 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tpage-break-after:avoid;\n\tfont-size:16.0pt;\n\tfont-family:\"Arial\",\"sans-serif\";\n\tcolor:black;}\nh3\n\t{mso-style-link:\"Heading 3 Char\";\n\tmargin-top:10.0pt;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tline-height:115%;\n\tpage-break-after:avoid;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";\n\tcolor:#4F81BD;}\np.MsoHeader, li.MsoHeader, div.MsoHeader\n\t{mso-style-link:\"Header Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoFooter, li.MsoFooter, div.MsoFooter\n\t{mso-style-link:\"Footer Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoTitle, li.MsoTitle, div.MsoTitle\n\t{mso-style-link:\"Title Char\";\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:12.0pt;\n\tmargin-left:0in;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpFirst, li.MsoTitleCxSpFirst, div.MsoTitleCxSpFirst\n\t{mso-style-link:\"Title Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpMiddle, li.MsoTitleCxSpMiddle, div.MsoTitleCxSpMiddle\n\t{mso-style-link:\"Title Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoTitleCxSpLast, li.MsoTitleCxSpLast, div.MsoTitleCxSpLast\n\t{mso-style-link:\"Title Char\";\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:12.0pt;\n\tmargin-left:0in;\n\ttext-align:center;\n\tfont-size:36.0pt;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\np.MsoSubtitle, li.MsoSubtitle, div.MsoSubtitle\n\t{mso-style-link:\"Subtitle Char\";\n\tmargin-top:6.0pt;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:center;\n\tline-height:115%;\n\tfont-size:24.0pt;\n\tfont-family:\"Bookman Old Style\",\"serif\";\n\tletter-spacing:.75pt;\n\tfont-weight:bold;}\np.MsoBodyText3, li.MsoBodyText3, div.MsoBodyText3\n\t{mso-style-link:\"Body Text 3 Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:12.0pt;\n\tfont-family:\"Verdana\",\"sans-serif\";\n\tcolor:black;}\na:link, span.MsoHyperlink\n\t{color:blue;\n\ttext-decoration:underline;}\na:visited, span.MsoHyperlinkFollowed\n\t{color:purple;\n\ttext-decoration:underline;}\npre\n\t{mso-style-link:\"HTML Preformatted Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:10.0pt;\n\tfont-family:\"Courier New\";}\np.MsoAcetate, li.MsoAcetate, div.MsoAcetate\n\t{mso-style-link:\"Balloon Text Char\";\n\tmargin:0in;\n\tmargin-bottom:.0001pt;\n\ttext-align:justify;\n\tfont-size:8.0pt;\n\tfont-family:\"Tahoma\",\"sans-serif\";}\np.MsoNoSpacing, li.MsoNoSpacing, div.MsoNoSpacing\n\t{margin:0in;\n\tmargin-bottom:.0001pt;\n\tfont-size:12.0pt;\n\tfont-family:\"Garamond\",\"serif\";}\np.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:.5in;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:.5in;\n\tmargin-bottom:.0001pt;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:.5in;\n\tmargin-bottom:.0001pt;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\np.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast\n\t{margin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:10.0pt;\n\tmargin-left:.5in;\n\tline-height:115%;\n\tfont-size:11.0pt;\n\tfont-family:\"Calibri\",\"sans-serif\";}\nspan.MsoSubtleEmphasis\n\t{color:gray;\n\tfont-style:italic;}\nspan.HeaderChar\n\t{mso-style-name:\"Header Char\";\n\tmso-style-link:Header;}\nspan.FooterChar\n\t{mso-style-name:\"Footer Char\";\n\tmso-style-link:Footer;}\nspan.Heading2Char\n\t{mso-style-name:\"Heading 2 Char\";\n\tmso-style-link:\"Heading 2\";\n\tfont-family:\"Arial\",\"sans-serif\";\n\tcolor:black;\n\tfont-weight:bold;}\nspan.BodyText3Char\n\t{mso-style-name:\"Body Text 3 Char\";\n\tmso-style-link:\"Body Text 3\";\n\tfont-family:\"Verdana\",\"sans-serif\";\n\tcolor:black;}\nspan.BalloonTextChar\n\t{mso-style-name:\"Balloon Text Char\";\n\tmso-style-link:\"Balloon Text\";\n\tfont-family:\"Tahoma\",\"sans-serif\";}\nspan.HTMLPreformattedChar\n\t{mso-style-name:\"HTML Preformatted Char\";\n\tmso-style-link:\"HTML Preformatted\";\n\tfont-family:\"Courier New\";}\nspan.TitleChar\n\t{mso-style-name:\"Title Char\";\n\tmso-style-link:Title;\n\tfont-family:\"Bernard MT Condensed\",\"serif\";\n\tcolor:green;\n\tletter-spacing:.25pt;}\nspan.Heading3Char\n\t{mso-style-name:\"Heading 3 Char\";\n\tmso-style-link:\"Heading 3\";\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:#4F81BD;\n\tfont-weight:bold;}\nspan.Heading1Char\n\t{mso-style-name:\"Heading 1 Char\";\n\tmso-style-link:\"Heading 1\";\n\tfont-family:\"Cambria\",\"serif\";\n\tcolor:green;\n\tfont-weight:bold;}\nspan.SubtitleChar\n\t{mso-style-name:\"Subtitle Char\";\n\tmso-style-link:Subtitle;\n\tfont-family:\"Bookman Old Style\",\"serif\";\n\tletter-spacing:.75pt;\n\tfont-weight:bold;}\np.SampleIO, li.SampleIO, div.SampleIO\n\t{mso-style-name:SampleIO;\n\tmargin-top:0in;\n\tmargin-right:0in;\n\tmargin-bottom:0in;\n\tmargin-left:16.4pt;\n\tmargin-bottom:.0001pt;\n\tfont-size:12.0pt;\n\tfont-family:\"Courier 10 Pitch\";}\n.MsoChpDefault\n\t{font-size:10.0pt;}\n /* Page Definitions */\n @page Section1\n\t{size:8.5in 11.0in;\n\tmargin:1.0in 1.0in 1.0in 1.0in;}\ndiv.Section1\n\t{page:Section1;}\n /* List Definitions */\n ol\n\t{margin-bottom:0in;}\nul\n\t{margin-bottom:0in;}\n--\u003e\n\u003c/style\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eYour friend is a biologist. He has just sequenced a DNA and wants to know about contribution of different genes in that DNA. Both Gene and DNA can be represented by a sequence of letters or strings. Given the sequence of a DNA \u003cb\u003eD\u003c/b\u003e and a Gene \u003cb\u003eG\u003c/b\u003e; your friend uses \u003cspan style\u003d\"line-height:\n115%\"\u003efollowing method to calculate the contribution.\u003c/span\u003e\u003c/p\u003e \n \u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eGenerate a list \u003cb\u003eP\u003c/b\u003e of proper non-empty prefixes of \u003cb\u003eG\u003c/b\u003e and another \u003cb\u003eS\u003c/b\u003e of proper non-empty suffixes of \u003cb\u003eG\u003c/b\u003e [1]. Additionally let the \u003cb\u003eL\u003c/b\u003e is list of all strings that is concatenation of a prefix and a suffix. So if \u003cb\u003eG \u003d ACCT\u003c/b\u003e then \u003cb\u003eP \u003d A, AC, ACC\u003c/b\u003e and \u003cb\u003eS \u003d T, CT, CCT\u003c/b\u003e and \u003cb\u003eL \u003d AT, ACT, ACCT, ACT, ACCT, ACCCT, ACCT, ACCCT, ACCCCT\u003c/b\u003e. If \u003cb\u003e|G| \u003d n\u003c/b\u003e then it is obvious that size of \u003cb\u003eL\u003c/b\u003e is \u003cb\u003e(n - 1)\u003csup\u003e2\u003c/sup\u003e\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e \n \u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eFor each element of \u003cb\u003eL\u003c/b\u003e, count number of times it occurs as substring in \u003cb\u003eD\u003c/b\u003e. Contribution of Gene \u003cb\u003eG\u003c/b\u003e in DNA \u003cb\u003eD\u003c/b\u003e is total of these values. For example if \u003cb\u003eD \u003d ACTACCTACCCCT\u003c/b\u003e then\u003c/span\u003e\u003c/p\u003e \n \u003cdiv align\u003d\"center\"\u003e \n \u003ctable class\u003d\"MsoTableGrid\" border\u003d\"1\" cellspacing\u003d\"0\" cellpadding\u003d\"0\" style\u003d\"margin-left:203.4pt;border-collapse:collapse;border:none\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eAT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border:solid black 1.0pt;\n border-left:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e0\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e0\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e0\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003eACCCCT\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e1\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"76\" valign\u003d\"top\" style\u003d\"width:56.8pt;border:solid black 1.0pt;\n border-top:none;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e\u003cb\u003eTotal\u003c/b\u003e\u003c/p\u003e \u003c/td\u003e \n \u003ctd width\u003d\"32\" valign\u003d\"top\" style\u003d\"width:24.2pt;border-top:none;border-left:none;\n border-bottom:solid black 1.0pt;border-right:solid black 1.0pt;padding:0in 5.4pt 0in 5.4pt\"\u003e \u003cp class\u003d\"MsoNormal\" align\u003d\"center\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt;\n text-align:center\"\u003e\u003cb\u003e6\u003c/b\u003e\u003c/p\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e \n \u003c/div\u003e \n \u003cp class\u003d\"MsoNormal\" style\u003d\"margin-top:10.0pt\"\u003eAs this process is very clumsy he wants to automate this process. As he is not a programmer, he needs your help. He will be very grateful if you kindly write him a program which will read the sequence of the DNA and the Gene, and will calculate contribution of the Gene in the DNA.\u003c/p\u003e \n 给定两个字符串D、G,取出G的“合适的”前缀(G所有前缀但不包括G本身),再取出G的“合适的”后缀(G所有后缀但不包括G本身),两个字符串前后拼接,显然,有\u003cb\u003e(n-1)\u003csup\u003e2\u003c/sup\u003e\u003c/b\u003e种选法。\u003cbr\u003e\n现在询问这些选法组成的字符串在D中出现的次数之和(即以子串形式在D中出现的次数)。\n"}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 20)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eEach case contains two lines. The first line contains a string denoting the sequence of DNA, and the second line contains another string denoting the Gene. The length of each string is less than \u003cb\u003e50000\u003c/b\u003e and consists of only \u003cb\u003eA, C, T\u003c/b\u003e and \u003cb\u003eG\u003c/b\u003e.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eFor each case, print the case number and the contribution, as described above.\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eACTACCTACCCCT\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eACCT\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eAAA\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eAAAA\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eAAAA\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eAAA\u003c/span\u003e\u003c/p\u003e "}},{"title":"Sample Output","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 6\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 4\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 3: 8\u003c/span\u003e\u003c/p\u003e "}},{"title":"Note","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eProper prefix (suffix) of a string \u003cb\u003eS\u003c/b\u003e is a prefix (suffix) of length smaller than \u003cb\u003e|S|\u003c/b\u003e. Here \u003cb\u003e|S|\u003c/b\u003e denotes length of \u003cb\u003eS\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e \n \u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eDataset is huge, use faster I/O methods.\u003c/span\u003e\u003c/p\u003e \n "}}]}