Cod sursa(job #1980549)

Utilizator Bodo171Bogdan Pop Bodo171 Data 13 mai 2017 13:23:02
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int nmax=1000005;
string s;
int A[nmax],B[nmax];
int i,mx,ind;
long long tot;
int main()
{
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");
    f>>s;
    //A[i]-impar
    //B[i]-par
    for(i=0;i<s.size();i++)
    {
        mx=A[i];
        while(i-mx>=0&&i+mx<s.size()&&s[i-mx]==s[i+mx])
            mx++;
        mx--;
        while(A[i]!=mx+1)
        {
            ind=i+A[i];
            if(min(mx+i-ind,A[i-A[i]])>A[ind])
              A[ind]=min(mx+i-ind,A[i-A[i]]);
            if(min(mx+i-ind,B[i-A[i]])>B[ind])
              B[ind]=min(mx+i-ind,B[i-A[i]]);
            A[i]++;
        }
        A[i]--;
        mx=B[i];
        while(i-mx+1>=0&&i+mx<s.size()&&s[i-mx+1]==s[i+mx])
          mx++;
        mx--;
        while(B[i]!=mx+1)
        {
            ind=i+B[i];
            if(min(i+mx-ind,A[i-B[i]+1])>A[ind])
               A[ind]=min(i+mx-ind,A[i-B[i]]);
            if(min(i+mx-ind,B[i-B[i]+1])>B[ind])
               B[ind]=min(i+mx-ind,B[i-B[i]+1]);
            B[i]++;
        }
        B[i]--;
        if(B[i]==-1) B[i]=0;
        tot+=1LL*(A[i]+B[i]+1);
    }
    g<<tot;
    return 0;
}