Pagini recente » preoji_bv_1 | Cod sursa (job #1842532) | Cod sursa (job #2352522) | Cod sursa (job #2195523) | Cod sursa (job #2909350)
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
long long ans;
string s;
vector<int> manacher_odd(string s) {
int n = s.size();
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(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
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;
}