Pagini recente » Cod sursa (job #2845083) | Cod sursa (job #1927044) | Cod sursa (job #3037738) | Cod sursa (job #1137028) | Cod sursa (job #1880242)
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1000003;
int n;
char sir[2 * N];
int sirx[2 * N];
void citire()
{
char tmp[N + 1];
fgets(tmp, N + 1, stdin);
n = strlen(tmp);
tmp[n - 1] = 0;
n--;
sir[0] = '#';
for(int i = 1; i <= 2 * n; i += 2)
{
sir[i] = tmp[i / 2];
sir[i + 1] = '#';
}
}
void manacher()
{
sirx[0] = 0;
sirx[1] = 1;
int c = 0;
int dr = 0;
int nr = 1;
for(int i = 2; i <= 2 * n; i++)
{
int j = c + (c - i);
//
// if(i < dr)
// {
//
// }
// else
// {
sirx[i] = 0;
//}
if(sir[i] == '#')
{
sirx[i]--;
}
else
{
nr++;
}
while(sir[i - sirx[i] - 2] == sir[i + sirx[i] + 2] && i - sirx[i] - 1 >= 0 && i + sirx[i] + 1 <= 2 * n)
{
sirx[i] += 2;
nr++;
}
//sirx[i] -= 2;
}
printf("%d", nr);
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
citire();
manacher();
return 0;
}