Pagini recente » Cod sursa (job #2131908) | Cod sursa (job #3184836) | Cod sursa (job #3215133) | Cod sursa (job #2372278) | Cod sursa (job #2376243)
#include <iostream>
#include <fstream>
const int MAXN = 1e6 * 2 + 2 + 5;
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int p[MAXN];
int main()
{
string input,s;
in>>input;
int n = input.size();
s += '$';
for(int i = 0; i < input.size(); i++){
s += '#';
s += input[i];
}
s += '#';
s += '$';
int center = 0,right = 0;
for(int i = 1; i < s.size() - 1; i++){
int mirror = 2 * center - i;
if(i < right)
p[i] = min(p[mirror],right - i);
while(p[i] < n and s[i + p[i] + 1] == s[i - p[i] - 1])
p[i]++;
if(i + p[i] > right){
right = i + p[i];
center = i;
}
}
long long ans = 0;
for(int i = 1; i < s.size() - 1; i++){
ans += p[i] / 2 + (p[i] % 2 != 0);
}
out<<ans<<"\n";;
return 0;
}