标签 - Manacher

? 解题记录 ? ? 洛谷 ? ? 哈希 ? ? Manacher ?    2018-07-11 16:50:30    286    0    0
描述:给定一个多边形,求对称轴数量。n <= 1000000   输入输出样例输入样例#1: 复制2 12 1 -1 2 -1 2 1 1 1 1 2 -1 2 -1 1 -2 1 -2 -1 -1 -1 -1 -2 1 -2 6 -1 1 -2 0 -1 -1 1 -1 2 0 1 1 输出样例#1: 复制4 2​​       
? 解题记录 ? ? BZOJ ? ? Manacher ?    2017-11-17 21:56:37    526    0    0
Description顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。 Input一行由小写英文字母组成的字符串S。 Output一行一个整数,表示最长双回文子串的长度。 Sample Inputbaacaabbacabb Sample Output12 HINT  样例说明从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。对
? 解题记录 ? ? Manacher ? ? 杂OJ ? ? 回文自动机 ?    2017-09-16 14:22:13    476    1    0
 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。 输入一个字符串Str,输出Str里最长回文子串的长度。   Input输入Str(Str的长度 <= 100000)Output输出最长回文子串的长度L。Sample Input daabaacSample Output 5 一个标准的Manacher,可以看看这篇博客,讲的很清楚:我就是“博客”。另外突然发现max,min好慢啊,而且其中的两种情况可以合并。附代码:#include<cstdio> #include<algorithm> #include<cs
? 解题记录 ? ? Manacher ? ? 杂OJ ?    2017-09-16 14:05:32    361    0    0
Description全部由小写字母构成且长度不超过 100000 的非空字符串,求最长的连续子字符串 使得该字符串与其反转字符串相等Input输入包含多组测试数据,每组数据一行,为一个长度不超过 100000 的非空字符串Output每组数据输出一行,为最长的连续子字符串的长度Sample Inputabcbad abccba abcba abbacc ccabbaSample Output5 6 5 4 4根据今天连WA带TLE的经验可以归纳出在写Manacher的时候需要注意这几点:    1、不同case之间要清零清干净&nb