Pagini recente » Cod sursa (job #2314333) | Cod sursa (job #38349) | Cod sursa (job #1803758) | Cod sursa (job #2300556) | Cod sursa (job #2387512)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n,c,r,l,dp[1000005];
char s[2000015],t[1000005];
long long rez;
int main() {
fin >> (t + 1);
n =(int) strlen(t + 1);
rez=n;
for (int i = 1; i <= n; ++i) {
s[2 * i - 1] = t[i];
s[2 * i] = '#'; }
n = 2 * n - 1;
s[n + 1] = '*';
s[0] = '$';
c=1;
r=1;
for(int i=2;i<=n;++i)
{
if(r>i)
dp[i]=min(r-i, dp[2*c-i]);
while(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]/2;
}
/*
rez=l;
c=1;
r=1;
for(i=2;i<=n;i++)
{
if(r>i)
dp[i]=min(r-i, dp[2*c-i]);
while(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]/2;
}*/
fout<<rez<<"\n";
return 0;
}