Pagini recente » Cod sursa (job #287198) | Cod sursa (job #1713999) | Cod sursa (job #3210269) | Cod sursa (job #1327505) | Cod sursa (job #2611605)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
typedef long long ll;
ll sol;
int n, center = 1;
string s, obj;
int manacher[2000005];
int main()
{
fin >> s;
n = s.length();
obj += '#';
for(int i = 0; i < n; ++i){
obj += s[i];
obj += '#';
}
n = obj.length();
manacher[0] = 0;
manacher[1] = 1;
for(int i = 2; i < n; ++i){
int mirror = 2 * center - i;
if(mirror - manacher[mirror] > center - manacher[center]){
manacher[i] = manacher[mirror];
}
else{
if(mirror >= center - manacher[center]) manacher[i] = center + manacher[center] - i;
int lft = i - manacher[i] - 1;
int rgt = i + manacher[i] + 1;
while(lft >= 0 && rgt < n){
if(obj[lft] == obj[rgt]) ++manacher[i];
else break;
--lft; ++rgt;
}
if(i + manacher[i] > center + manacher[center])
center = i;
}
sol = sol + 1LL * (1LL * manacher[i] + 1LL) / 2LL;
}
fout << sol + 1LL;
return 0;
}