Pagini recente » Cod sursa (job #2048126) | Cod sursa (job #1597168) | Cod sursa (job #1816217) | Cod sursa (job #1760316) | Cod sursa (job #1570298)
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int maxn = 1000005;
char T[maxn];
char s[maxn];
int p[maxn];
int main()
{
in.getline(T + 1, maxn);
int n = strlen(T+1);
for(int i = 1; i <= n; i++)
{
if(i%2 == 0)
s[i*2] = '#';
else
s[i*2-1] = T[i];
}
n = n * 2;
int c = 1;
int r = 1;
for(int i = 2; i <= n; i++)
{
int i_ = c - (i - c);
if(p[i_] + i < r)
p[i] = p[i_];
else
{
p[i] = r - i;
while(s[i + p[i] + 1] == s[i - p[i] - 1])
++p[i];
}
if(i + p[i] > r)
{
c = i;
r = i + p[i];
}
}
int nr = 0;
for(int i = 1; i <= n; i++)
p[i] = p[i] * 2;
for(int i = 1; i <= n; i++)
nr += p[i] * (p[i]+1) / 2;
out << nr << '\n';
return 0;
}