Cod sursa(job #1857925)

Utilizator geo_furduifurdui geo geo_furdui Data 26 ianuarie 2017 20:48:02
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("message.in");
ofstream cout ("message.out");
char s[2000001],t[1000001];
int n=-1,centru,righ,maxim,pmaxim,l[2000001];
void read ()
{ int i=0;
    cin.getline(t,1000001);
    while(t[i]!=0)
    {
        s[++n]='#';
        s[++n]=t[i]; i++;
    }
    s[++n]='#';
}
int expand (int aa,int bb,int poz)
{
    while(3>2 && aa>=0 && bb<=n)
    {
            if(s[aa]!=s[bb]) return poz-aa-1;
        aa--; ++bb;
    }
    return poz-aa-1;
}
void solve_here ()
{
    centru=0; righ=0;
    for(int i=1;i<n;i++)
    {
        if(i>righ) l[i]=expand(i,i,i);
        else
        {
            int c=min(l[centru-i+centru],righ-centru);
            l[i]=expand(i-c-1,i+c+1,i);
        }
        if(l[i]+i>righ) righ=l[i]+i,centru=i;
    }
}
void write ()
{ int sum=0;
    for(int i=0;i<n;i++)
    {
            sum=sum+(l[i]+1)/2;
    }
    cout<<sum;
}
int main()
{
    read();
    solve_here();
    write();
    cin.close();
    cout.close();
    return 0;
}