Pagini recente » Cod sursa (job #818418) | Cod sursa (job #1362653) | Cod sursa (job #2862899) | Cod sursa (job #1399238) | Cod sursa (job #1227432)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define MAX_LENGTH 200001
using namespace std;
string create_aux(string s)
{
string res;
int i, n = s.length();
if(!n)
res = " ";
else
{
res = " ";
for(i = 0 ; i < n ; i++)
res += " " + s.substr(i, 1);
}
res += " ";
return res;
}
int main()
{
string s, T;
int n, mid, r, aux, p[MAX_LENGTH];
long long sum = 0;
fstream f("pscpld.in", ios::in);
fstream g("pscpld.out", ios::out);
f >> s;
T = create_aux(s);
//cout << T;
n = T.length();
mid = r = 0;
for(int i = 1 ; i < n-1 ; i++)
{
aux = mid - (i - mid);
if(r > i)
p[i] = min(r - i, p[aux]);
else
p[i] = 0;
while(T[i + 1 + p[i]] == T[i - 1 - p[i]])
p[i]++;
//cout << p[i] << " ";
if(i + p[i] > r)
{
r = i + p[i];
mid = i;
}
sum += (p[i] + 1) / 2;
}
g << sum;
return 0;
}