Cod sursa(job #1857945)

Utilizator geo_furduifurdui geo geo_furdui Data 26 ianuarie 2017 21:06:11
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
char t[1000010],s[2000011];
int n=0,r,c,l[3000012],poz; long long rez;
void read ()
{
    cin.getline(t,1000005);
    int m=strlen(t); s[0]='#';
    for(int i=0;i<m;i++)
        s[++n]=t[i],s[++n]='#';
    s[++n]='#';
}
void expand (int st,int dr)
{
    while(st>=0 && dr<=n && s[st]==s[dr])
    {
        l[poz]++;
        st--; dr++;
    }
}
void solve ()
{
    c=0; r=0;
    for(int i=1;i<=n;i++)
    {
        if(i<=r) l[i]=l[2*c-i]; poz=i;
        expand(i-l[i]-1,i+l[i]+1);
        if(i+l[i]>r) r=i+l[i],c=i;
        rez=rez+(l[i]+1)/2;
    }
}
void write ()
{
    cout<<rez<<"\n";
}
int main()
{
    read();
    solve();
    write();
    cin.close();
    cout.close();
    return 0;
}