标签 - 回文自动机

? 解题记录 ? ? 杂OJ ? ? 回文自动机 ?    2018-03-10 09:11:00    578    0    0
【题目描述】对于给定的字符串S,我们想知道它有多少个不同的回文子串。 【输入】一行,一个长度不超过100000的仅小写字母构成的字符串。 【输出】一个整数,代表不同的回文子串个数。 【输入样例】abcd 【输出样例】4 【提示】有20%的数据,输入字符串的长度不超过1000。 本题有后缀数组的O(n log n)算法,但是既然咱们有回文自动机不是板子题就轻松切掉了嘛。于是又水了一题…… #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int
? 解题记录 ? ? Codeforces ? ? 回文自动机 ?    2017-11-25 12:00:35    436    0    0
DescriptionAfter finishing his homework, our problem setter Federmann decided to kill time by hangingaround online. He found a cool chat room that discusses competitive programming. Federmannhas already joined lot of such chat rooms, but this one is special. Once he entered thechat room, he noticed
? 解题记录 ? ? 杂OJ ? ? 回文自动机 ?    2017-11-25 11:51:21    400    0    0
411. Petya the Hero Time limit per test: 0.25 second(s) Memory limit: 65536 kilobytes input: standard output: standard Petya has come back from the Berland-Birland War, and now he is fond of gathering his friends and narrating his heroic deeds. You have probably heard the story telling that Petya,
? 解题记录 ? ? BZOJ ? ? 回文自动机 ?    2017-11-23 11:13:58    591    0    0
Description考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最 大出现值。  Input输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。  Output输出一个整数,为逝查回文子串的最大出现值。  Sample Input【样例输入l】 abacaba 【样例输入2] www Sample Output【样例输出l】 7 【样例输出2] 4 HINT  一个串是回文的,当且仅当它从左到右读和从
? 解题记录 ? ? 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