Pagini recente » Cod sursa (job #2320546) | Cod sursa (job #1582854) | Cod sursa (job #1304025) | Cod sursa (job #1563076) | Cod sursa (job #880733)
Cod sursa(job #880733)
#include <cstdio>
const int MAX_SIZE(1000010);
char v [MAX_SIZE];
char s [MAX_SIZE << 1];
int dp [MAX_SIZE << 1];
int vlength, length;
inline int min (int a, int b)
{
return a < b ? a : b;
}
inline void read (void)
{
std::freopen("pscpld.in","r",stdin);
std::gets(v);
s[0] = '$';
int i, j;
for (i = 0, j = 1 ; v[i] ; ++i, ++j)
{
s[j] = ' ';
++j;
s[j] = v[i];
}
s[j] = ' ';
++j;
s[j] = '#';
length = j;
vlength = i;
std::fclose(stdin);
}
inline void print (void)
{
std::freopen("pscpld.out","w",stdout);
long long result(0);
for (int index(1) ; index <= length ; ++index)
result += (dp[index] >> 1);
std::printf("%lld",result + vlength);
std::fclose(stdout);
}
inline void Manacher (void)
{
int position, center(0), right(0), mirror;
for (position = 1 ; position <= length ; ++position)
{
mirror = center - (position - center);
dp[position] = position < right ? min(dp[mirror],right - position) : 0;
while (s[position + dp[position] + 1] == s[position - dp[position] - 1])
++dp[position];
if (position + dp[position] > right)
{
right = position + dp[position];
center = position;
}
}
}
int main (void)
{
read();
Manacher();
print();
return 0;
}