Pagini recente » Cod sursa (job #281889) | Cod sursa (job #1054746) | Cod sursa (job #255215) | Cod sursa (job #2589246) | Cod sursa (job #2795413)
#include <iostream>
#include <stdio.h>
#include <ctype.h>
using namespace std;
const int NMAX = 1000000;
int dpRmax[NMAX * 2 + 3];
char s[NMAX*2 + 3];
inline int mymin(int a, int b);
int main()
{
int n, ccur, rcur, cnou, rnou;
long long sum = 0;
char ch;
s[0] = '&';
s[1] = '*';
n = 2;
FILE *fin = fopen("pscpld.in", "r");
while (isalpha(ch = fgetc(fin)))
{
s[n++] = ch;
s[n++] = '*';
}
fclose(fin);
ccur = rcur = 0;
for (cnou = 2; cnou < n; cnou++)
{
if (ccur + rcur <= cnou)
rnou = 0;
else
rnou = mymin(dpRmax[cnou], (ccur << 1) - cnou);
while (s[cnou + rnou + 1] == s[cnou - rnou - 1])
rnou++;
dpRmax[cnou] = rnou;
sum += (long long)((rnou + 1) >> 1);
if (cnou + rnou > ccur + rcur)
{
ccur = cnou;
rcur = rnou;
}
}
FILE *fout = fopen("pscpld.out", "w");
fprintf(fout, "%lld", sum);
fclose(fout);
return 0;
}
inline int mymin(int a, int b)
{
if (a < b)
return a;
return b;
}