Pagini recente » Cod sursa (job #988334) | Cod sursa (job #1995357) | Cod sursa (job #1943703) | Cod sursa (job #1578411) | Cod sursa (job #2376228)
#include <iostream>
#include <fstream>
const int MAXN = 1000000 * 2 + 5;
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int p[MAXN];
int main()
{
string input,s;
in>>input;
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(); i++){
int mirror = 2 * center - i;
if(i < right)
p[i] = min(p[mirror],right - i);
while(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 = 0; i < s.size(); i++)
ans += p[i] / 2 + (p[i] % 2 != 0);
out<<ans<<"\n";;
return 0;
}