Pagini recente » Cod sursa (job #2976253) | Cod sursa (job #2955220) | Cod sursa (job #488298) | Cod sursa (job #1924735) | Cod sursa (job #2713548)
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int Max = 1e6 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
char s[Max]="";
char sir[2*Max]="";
int n;
void read()
{
f>>s;
int i;
int it = -1;
for(i=0; s[i]; i++)
{
sir[++it] = '#';
sir[++it] = s[i];
}
sir[++it] = '#';
n = it;
}
int dp[2*Max];
void solve()
{
int has_pair = -1;
int pair_center;
int i;
int last = n;
for(i=0; i<=n; i++)
{
int j;
if(has_pair >= i)
{
int delta = has_pair - pair_center;
j = min(dp[pair_center - delta],has_pair - i + 1);
}
else
j = 1;
while(i - j >=0 and i+j <= last and sir[i-j] == sir[i+j])
++j;
dp[i] = j;
if(i+j - 1 > has_pair)
{
has_pair = i + j - 1;
pair_center = i;
}
}
int ans = 0;
// for(i=0; sir[i]; i++)
// cout<<sir[i]<<' ';
// cout<<'\n';
// for(i=0; sir[i]; i++)
// cout<<dp[i]<<' ';
// cout<<'\n';
for(i=0; i<=n; i++)
ans+= dp[i] / 2;
g<<ans;
}
void restart()
{
}
int32_t main()
{
nos();
read();
solve();
restart();
return 0;
}