Pagini recente » Cod sursa (job #3313644) | Cod sursa (job #3323709) | Cod sursa (job #3333454) | Cod sursa (job #3321752) | Cod sursa (job #3349963)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[1000005],t[2000010];
int r[2000010];
int main()
{
fin>>s;
int ns=strlen(s);
int n=0;
t[n++]='@';
for(int i=0;i<ns;i++)
{
t[n++]='#';
t[n++]=s[i];
}
t[n++]='#';
t[n++]='$';
long long tot=0;
int c=0,m=0; // c=centru, m=margine dreapta
// 2. Algoritmul Manacher
for(int i=1;i<n-1;i++)
{
int ogl=2*c-i; // oglinda lui i fata de c
if(i<m)
r[i]=min(m-i,r[ogl]);
// Extindere fara spatii la operatori
while(t[i+(1+r[i])]==t[i-(1+r[i])])
r[i]++;
// Update centru si margine
if(i+r[i]>m)
{
c=i;
m=i+r[i];
}
// Adaugam numarul de palindromuri gasite
tot+=(r[i]+1)/2;
}
fout<<tot;
return 0;
}