Cod sursa(job #1570298)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 16 ianuarie 2016 12:41:50
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int maxn = 1000005;
char T[maxn];
char s[maxn];
int p[maxn];

int main()
{
    in.getline(T + 1, maxn);
    int n = strlen(T+1);
    for(int i = 1; i <= n; i++)
    {
        if(i%2 == 0)
            s[i*2] = '#';
        else
            s[i*2-1] = T[i];
    }
    n = n * 2;
    int c = 1;
    int r = 1;
    for(int i = 2; i <= n; i++)
    {
        int i_ = c - (i - c);
        if(p[i_] + i < r)
            p[i] = p[i_];
        else
        {
            p[i] = r - i;
            while(s[i + p[i] + 1] == s[i - p[i] - 1])
                ++p[i];
        }
        if(i + p[i] > r)
        {
            c = i;
            r = i + p[i];
        }
    }
    int nr = 0;
    for(int i = 1; i <= n; i++)
        p[i] = p[i] * 2;
    for(int i = 1; i <= n; i++)
        nr += p[i] * (p[i]+1) / 2;
    out << nr << '\n';
    return 0;
}