{"trustable":false,"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n\u003cbr\u003e马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人在 1975 年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了不起的。\u003cp\u003e\n对于回文串想必大家都不陌生,就是正读反读都一样的字符串,比如 \"bob\", \"level\", \"noon\" 等等。\u003cp\u003e\n那么如何在一个字符串中找出最长回文子串呢,可以以每一个字符为中心,向两边寻找回文子串,在遍历完整个数组后,就可以找到最长的回文子串。但是这个方法的时间复杂度为 O(n*n),并不是很高效。\u003cp\u003e\n那么 O(n)的马拉车算法到底是怎么样的呢?\u003cp\u003e\n请看题意:\u003cp\u003e\n A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string \"ABCDEDCBA\" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left. \n \u003cbr\u003e \n \u003cbr\u003eNow give you a string S, you should count how many palindromes in any consecutive substring of S. \n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases in the input. Each case contains a non-empty string which has no more than 5000 characters. \n\u003cbr\u003e \n\u003cbr\u003eProceed to the end of file. \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"A single line with the number of palindrome substrings for each case. \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003eaba\naa\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e4\n3\u003c/pre\u003e"}},{"title":"出题人有话说:","value":{"format":"HTML","content":"其实这题和马拉车算法属于八竿子打不着的关系,只是想让你们了解一下马拉车算法求最长回文串长度。"}}]}