>Link
ybtoj回文子串
>解题思路
寻找回文子串,我们可以从这个子串的中心逐渐向外扩散,如果左边的子串等于右边的子串倒过来,就说明这个子串为回文子串。
所以我们枚举每一个点为中心,二分查找最长的扩散长度,注意这里要处理子串长度为奇数和偶数的不同情况,特殊的,如果长度为偶数,中心点是没有字符的。
如何判断“左边的子串等于右边的子串倒过来”呢?其实直接把这个字符串正过来、倒过来分别做一个哈希就行了
时间复杂度大概为 O ( n l o g n ) O(nlogn) O(nlogn)
>代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
#define ull unsigned long long
using namespace std;
int C, n, l, r, mid, ans;
ull a[N], hf[N], hb[N];
string s;
void find ()
{
for (int i = 1; i <= n; i++)
{
l = 1, r = n;
while (l <= r)
{
mid = (l + r) / 2;
if (i + mid > n || i - mid < 1) {r = mid - 1; continue;}
if (hf[i - 1] - hf[i - 1 - mid] * a[mid]
== hb[i + 1] - hb[i + 1 + mid] * a[mid])
{
ans = max (ans, 2 * mid + 1);
l = mid + 1;
}
else r = mid - 1;
}
l = 1, r = n;
while (l <= r)
{
mid = (l + r) / 2;
if (i + mid > n || i - mid + 1 < 1) {r = mid - 1; continue;}
if (hf[i] - hf[i - mid] * a[mid]
== hb[i + 1] - hb[i + 1 + mid] * a[mid])
{
ans = max (ans, 2 * mid);
l = mid + 1;
}
else r = mid - 1;
}
}
}
int main()
{
cin >> s;
a[0] = 1;
for (int i = 1; i <= 1000000; i++) a[i] = a[i - 1] * 109;
while (s != "END")
{
memset (hf, 0, sizeof (hf));
memset (hb, 0, sizeof (hb));
C++; ans = 1;
n = s.size();
s = " " + s;
for (int i = 1; i <= n; i++)
hf[i] = hf[i - 1] * 109 + s[i] - 'a' + 1;
for (int i = n; i >= 1; i--)
hb[i] = hb[i + 1] * 109 + s[i] - 'a' + 1;
find ();
printf ("Case %d: %d\n", C, ans);
cin >> s;
}
return 0;
}