Pagini recente » Cod sursa (job #1192519) | Cod sursa (job #165988) | Cod sursa (job #2684451) | Cod sursa (job #2280541) | Cod sursa (job #2387485)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n,i,j,c,r,l,nr,dp[1000005];
char s[2000015];
string t;
long long rez;
int main() {
getline(fin,t);
n=1;
s[1]='#';
for(i=0;i<t.size();i++)
s[++n]=t[i], s[++n]='#';
c=1;
r=1;
for(i=2;i<=n;i++)
{
j=c-(i-c);
if(r>i)
dp[i]=min(r-i, dp[j]);
while(i+dp[i]<=n && i-dp[i]>0 && s[i+dp[i]]==s[i-dp[i]])
dp[i]++;
dp[i]--;
if(i+dp[i]>r)
c=i, r=dp[i];
rez+=1LL*(dp[i]+1)/2;
}
fout<<rez<<"\n";
}