{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eString matching is a common type of problem in computer science. One string matching problem is as following:\u003cbr\u003e\u003cbr\u003eGiven a string $s[0 \\ldots len-1]$, please calculate the length of the longest common prefix of $s[i \\ldots len-1]$ and $s[0 \\ldots len-1]$ for each $i \u0026gt; 0$.\u003cbr\u003e\u003cbr\u003eI believe everyone can do it by brute force.\u003cbr\u003eThe pseudo code of the brute force approach is as the following:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7ff34e1d671470e09b27beabb36fa62e?v\u003d1725396342\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eWe are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$, denoting the number of test cases.\u003cbr\u003eEach test case contains one string in a line consisting of printable ASCII characters except space.\u003cbr\u003e\u003cbr\u003e* $1 \\le T \\le 30$\u003cbr\u003e\u003cbr\u003e* string length $\\le 10^6$ for every string"}},{"title":"Output","value":{"format":"HTML","content":"For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n_Happy_New_Year_\r\nywwyww\r\nzjczzzjczjczzzjc\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\r\n7\r\n32\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}