Pagini recente » Cod sursa (job #50950) | Cod sursa (job #1072808) | Cod sursa (job #532974) | Istoria paginii utilizator/pincucatalin | Cod sursa (job #790638)
Cod sursa(job #790638)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
#define nmax 2000010
char B[nmax], A[nmax];
int lg[nmax];
long long ans = 1;
int N, L, R, C = 1, now;
int main()
{
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int i;
in >> B;
now = strlen(B);
for(i = 0; i < now; i++)
{
A[++N] = B[i];
if(i < now - 1) A[++N] = '#';
}
lg[1] = 1;
for(i = 2; i <= N; i++)
{
lg[i] = max(min(lg[2 * C - i] - 1, C + lg[C] - i), 1);
L = i - lg[i];
R = i + lg[i];
while(L > 0 && R <= N && A[L] == A[R])
{
L --;
R ++;
lg[i] ++;
}
if(A[i] == '#') ans += lg[i] / 2;
else ans += (lg[i] + 1) / 2;
if(i + lg[i] > C + lg[C]) C = i;
}
out << ans;
return 0;
}