The Manacher algorithm is a linear algorithm to calculate the total number of palindromic substring of the given string (also the longest palindromic substring). The problem has other solutions, including O(n^2) dynamic programming and O(nlogn) rolling hash + binary search result.
// for each position i=0…n−1 we'll find the values d1[i] and d2[i], denoting the number of palindromes
// accordingly with odd and even lengths with centers in the position i.
// For instance, string s=abababc has three palindromes with odd length with centers in the position s[3]=b, i. e. d1[3]=3:
// a b a b a b
// _
// _ _ _
// _ _ _ _ _
// And string s=cbaabd has two palindromes with even length with centers in the position s[3]=a, i. e. d2[3]=2:
// c b a a b d
// _ _
// _ _ _ _
vector<int> GetD1(string_view s) {
int n = s.size();
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
return d1;
}
vector<int> GetD2(string_view s) {
int n = s.size();
vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
k++;
}
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k ;
}
}
return d2;
}