Cod sursa(job #475345)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 6 august 2010 18:29:49
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <string>
using namespace std;

const int NMAX=1000005;

int L[2][NMAX],N;
string s;

int main()
{
    ifstream fin("pscpld.in");
    getline(fin,s);
    
    N=s.length();
    
    int st=0,dr=0,i,j,p,q;
    L[0][0]=0;
    if (s[0]==s[1]) L[0][0]=1,dr=1;
    L[1][0]=1;
    
    for (i=1;i<N;++i)
    {
      //printf("i=%d st=%d dr=%d\n",i,st,dr);
      if (i<dr)
      {
        j=st+dr-i;
        L[0][i]=min(L[0][j-1], j-st);
        if (i+L[0][i]==dr)
        {
           p=i-L[0][i]+1;q=dr;
           while (p>0 && q<N-1 && s[p-1]==s[q+1]) ++L[0][i],--p,++q;
        }
        
        L[1][i]=min(L[1][j],j-st+1);
        if (i+L[1][i]-1==dr)
           while ((st=i-L[1][i]+1)>0 && dr<N-1 && s[st-1]==s[dr+1]) ++L[1][i],--st,++dr;
        
        if (q>dr) st=p,dr=q;
      }
      else
      {
        L[0][i]=0;
        p=i+1;q=i;
        while (p>0 && q<N-1 && s[p-1]==s[q+1]) ++L[0][i],--p,++q;
       
        L[1][i]=1;
        int _p=i,_q=i;
        while (_p>0 && _q<N-1 && s[_p-1]==s[_q+1]) ++L[1][i],--_p,++_q;
        
        if (_q > q) p=_p,q=_q;
        if (q > dr) st=p,dr=q;
      }
    } 
    long long ans=0;
    for (i=0;i<N;++i) ans+=L[1][i];// printf("L[1][%d]=%d\n",i,L[1][i]);
    for (i=0;i<N-1;++i) ans+=L[0][i]; //printf("L[0][%d]=%d\n",i,L[0][i]);;
    
    ofstream fout("pscpld.out");
    fout<<ans<<"\n";
      
    return 0;
}