Pagini recente » Cod sursa (job #669937) | Cod sursa (job #569417) | Cod sursa (job #1830932) | Cod sursa (job #3185624) | Cod sursa (job #2910921)
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
long long ans;
char s[2*N];
vector<int> manacher_odd(char s[]) {
int n = strlen(s);
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, min(r - i, p[l + (r - i)]));
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return p;
}
vector<int> manacher(char s[]) {
char t[2*N];
int m=0;
for(int i=0;s[i];i++) {
t[m++]='#',t[m++]=s[i];
}
t[m++]='#';//cout<<t<<" ";
auto res = manacher_odd(t);
return vector<int>(begin(res) + 1, end(res) - 1);
}
int main()
{
fin>>s;
vector<int>p=manacher(s);
for(auto x:p) ans+=x/2;
fout<<ans;
return 0;
}