Cod sursa(job #1883474)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 17 februarie 2017 23:35:05
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int N = 2000005;
 
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;
 
    for(int i = 2; i <= 2 * n; i++)
    {
        int j = c + (c - i);
 
        if(i < dr)
        {
            if(dr - i < sirx[j])
            {
                sirx[i] = dr - i;
            }
            else
            {
                sirx[i] = sirx[j];
            }
        }
        else
        {
            sirx[i] = 0;
        }
 
        while(i - sirx[i] - 1 >= 0 && i + sirx[i] + 1 <= 2 * n && sir[i - sirx[i] - 1] == sir[i + sirx[i] + 1])
        {
            sirx[i]++;
        }
 
        if(sirx[i] + i > dr)
        {
            dr = i + sirx[i];
            c = i;
        }
    }
 
    long long nr = 0;
 
    for(int i = 1; i <= 2 * n; i++)
    {
        if(sirx[i] % 2 == 0)
        {
            nr += sirx[i] / 2;
        }
        else
        {
            nr += sirx[i] / 2 + 1;
        }
    }
 
    printf("%d", nr);
}
 
int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
 
    citire();
    manacher();
 
    return 0;
}