Pagini recente » Cod sursa (job #1862136) | Cod sursa (job #1977032)
#include <fstream>
#include <cstring>
#define Nmax 2000005
#define LL long long
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n,lg[Nmax];
LL rez;
char s[Nmax],s2[Nmax];
int main()
{
f>>s+1;
n = strlen(s+1);
int nr = 1;
for (int i=1;i<=n;i++)
{
s2[i*2-1] = '*';
s2[i*2] = s[i];
}
n = n*2+1;
s2[n] = '*';
int index = 0,c;
for (int i=1;i<=n;i++)
{
if (i<index)
{
lg[i] = min(index - i + 1, lg[c - (i-c)]);
}
while (i-lg[i]>=1 && i+lg[i]<=n && s2[i-lg[i]]==s2[i+lg[i]])
lg[i]++;
rez += lg[i]/2;
if (i+lg[i]>index)
{
index = i+lg[i]-1;
c = i;
}
}
g<<rez;
return 0;
}