回文串

回文串

描述

给定一个字符串，求出该字符串有多少子串是回文串。

子串：字符串中连续的一段。比如字符串 abcd 里，bc、abc、a、bcd 都是子串。

回文串：字符串倒序写出来和该字符串相同。比如aba，倒序写出来也是aba，故 aba 是回文串。而 abab 不是回文串，因为倒过来写是 baba。

输入

输入一个字符串。

输

输出子串是回文串的个数。

样例 1 输入

样例 1 输

样例 1 解释

abab，abab，abab abab，abab，abab

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 50%的数据，字符串长度不超过 500； 对于 70%的数据，字符串长度不超过 2000；

对于 100%的数据，字符串长度不超过 500000。字符串为 26 个小写字母组成。

时间：2 sec

空间：512 MB

提示

[[[https://segmentfault.com/a/1190000003914228]

[这篇文章是求最长的回文串的，那么如何求回文串的数目呢？可以发现manacher 算法将每个位置为中心能延展出的最长回文串求出来了，那么这个最长回文串的一半（上取整） 就是以该点作为中心的回文串数目。]

[注意答案要用long long。]

代码

#include <iostream> #include<algorithm>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

const int N = 500005;

/* 请在这里定义你需要的全局变量 */

//s:变化后的s数组

//len:每个位置能向左拓展的最大长度(回文半径) char s[N * 2];

int len[N * 2];

// 计算str中有多少个回文子串

// 返回值：子串的数目

long long getAnswer(string str) {

/* 请在这里设计你的算法 */

int n = str.size();

//将字符串变为#a#b#c#d#这样的形式，下方认为#是0

for (int i = n; i; --i)

s[i << 1] = str[i - 1], s[i << 1 | 1] = 0;

//边界(位置0和n+1)设为不同于#的东西(即1和2)

n = n << 1 | 1;

s[1] = 0, s[0] = 1, s[n + 1] = 2;

//manacher算法

int cur = 1;

long long ans = 0;

for (int i = 2; i <= n; ++i)

{

int &now = len[i], pos = (cur << 1) - i;

now = max(min(len[pos], cur + len[cur] - i), 0);

while (s[i - now - 1] == s[i + now + 1])

++now;

if (i + now > cur + len[cur])

cur = i;

ans += ((now + 1) >> 1);//相当于now/2取上界

}

return ans;

}

// ================= 代码实现结束 =================

char _s[N];

int main() {

scanf("%s", _s + 1);

printf("%lld\n", getAnswer(_s + 1));

return 0;

}