Cod sursa(job #908368)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 9 martie 2013 12:28:45
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <cstring>
#define N 2000010
using namespace std;

string s;
int Pal[N], L, C, R, n, i, j;
long long k;

int main()
{
    ifstream fi("pscpld.in");
    ofstream fo("pscpld.out");
    fi >> s;
    n = s.length();
    n += n-1;
    C = R = 0;
    for(i = 1; i < n; i++)
    if(R <= i)
    {
        L = C = R = i;
        if(i%2 == 1)
        {
            R++;
            L--;
        }
        while(L >= 0 and R < N and s[L/2] == s[R/2])
            L -= 2, R += 2;
        L += 2; R -= 2;
        if(s[L/2] != s[R/2]) L = R = i;
        C = i; Pal[i] = (R - C + 1)/2;
        if(i%2 == 0) Pal[i]++;
    }
    else
    {
        j = 2*C - i;
        if(Pal[j] < ((R - i + 1)/2))
        {
            Pal[i] = Pal[j];
            continue;
        }
        C = i;
        L = 2*C - R;
        while(L >= 0 and R < N and s[L/2] == s[R/2]) L -= 2, R += 2;
        L += 2; R -= 2;
        Pal[i] = (R - C + 1)/2;
        if(i%2 == 0) Pal[i]++;
    }
    for(i = 1, k = 1; i < n; i++) k += (long long)Pal[i];
    fo << k << "\n";
    return 0;
}