Cod sursa(job #2275711)

Utilizator raskyNichita Sincarenco rasky Data 3 noiembrie 2018 14:07:33
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int MAX = 2e6 + 3;
char s[MAX], a[MAX];
int v[MAX], n;

int main()
{
    ifstream fcin("pscpld.in");
    ofstream fcout("pscpld.out");

    fcin>>s;

    n = strlen(s);
    for(int i=0; i<n; i++)
        a[(i+1)*2 ] = s[i];

    n = 2*n +3;
    a[0]=a[n-1]= '$';

    for(int i=1; i<=n-2; i=i+2)
        a[i] = '#';

    int imax=1, lim=1;
    v[1] = 1;
    for(int i=2; i<n-1; i++)
    {
        if(i==lim+1)
        {
            imax = i;
            while(a[i- v[i] ] == a[i+ v[i] ])
                ++v[i];
            lim = i + v[i] - 1;
        }
           else
           {
               if( i + v[2*imax-i] - 1 < lim )
               {
                   v[i] = v[2*imax - i];
               }
               else {
                    imax = i;
                    v[i] = lim - i + 1;
                    while(a[i- v[i] ] == a[i+ v[i] ])
                        ++v[i];
                    lim = i + v[i] - 1;
               }
           }
    }

    long long s = 0;

    for(int i=1; i<=n-1; i++)
        s = s + v[i] / 2;
    fcout << s;
    return 0;
}