Pagini recente » Cod sursa (job #1252624) | Cod sursa (job #1175880) | Cod sursa (job #1037486) | Cod sursa (job #2442767) | Cod sursa (job #1099069)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[2000010];
int N;
long long sol;
int P[2000010];
void pscpld()
{
int best = 0;
for (int i = 1; i <= N; ++i)
{
if (best + P[best] >= i)
P[i] = min(best + P[best] - i, P[2 * best - i]);
while (i - P[i] - 1 > 0 && i + P[i] + 1 <= N && s[i - P[i] - 1] == s[i + P[i] + 1])
++P[i];
if (i + P[i] >= best + P[best])
best = i;
}
}
int main()
{
fin.getline(s + 1, 1000001);
N = strlen(s + 1);
for (int i = 2 * N + 1; i > 0; --i)
{
if (i % 2 == 1)
s[i] = ' ';
else
s[i] = s[i / 2];
}
N = 2 * N + 1;
pscpld();
for (int i = 2; i <= N - 1; ++i)
{
if ((i - 1) % 2 == 1)
sol += (P[i] + 1) / 2;
else
sol += P[i] / 2;
}
fout << sol << '\n';
fin.close();
fout.close();
return 0;
}