Cod sursa(job #1605304)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 18 februarie 2016 21:42:47
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pii pair<int,int>
#define tii tuple <int,int,int>
#define N 2000005
#define Nn 400005
#define mod 1000000005
#define X first
#define Y second
#define eps 0.0000000001
#define all(x) x.begin(),x.end()
#define tot(x) x+1,x+n+1
using namespace std;
string s,t;
int sol,n,id,mx,L[N],i;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{

    fin>>s;
    n=s.size();
    for(i=0; i<n; i++)
    {
        t+=' ';
        t+=s[i];
    }
    t+=' ';

    id=mx=0;
    n*=2;
    for(i=1; i<n; i++)
    {
        if(i<mx)
        {
            if(mx-i>=L[2*id-i])
                L[i]=L[2*id-i];
            else
                L[i]=mx-i;
        }
        else
            L[i]=1;
        while(t[i+L[i]]==t[i-L[i]])
            L[i]++;
        if(i+L[i]>mx)
        {
            mx=L[i]+i;
            id=i;
        }
        sol+=L[i]/2;
    }
    fout<<sol;
    return 0;
}