Cod sursa(job #2262541)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 17 octombrie 2018 16:26:09
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
using namespace std;
ifstream fi ("pscpld.in");
ofstream fo ("pscpld.out");
string s;
char sir[2000005];
long long lg,capatdr,mij,st,dr,simetric,sum,dist;
long long dp[2000005];
int main()
{
    fi>>s;
    lg++;
    sir[lg]='*';
    lg++;
    for (int i=0;i<s.size();i++)
    {
        sir[lg]=s[i];
        lg++;
        sir[lg]='*';
        lg++;
    }
    lg--;
    capatdr=0;
    mij=0;
    for (int i=1;i<=lg;i++)
    {
        if (i>=capatdr)
        {
            dp[i]=1;
            st=i-1;dr=i+1;
            while (st>=1 and dr<=lg and sir[st]==sir[dr])
            {
                st--;dr++;dp[i]++;
            }
            mij=i;capatdr=i+dp[i]-1;
        }
        else
        {
            dist=i-mij;
            simetric=mij-dist;
            dp[i]=min(dp[simetric],capatdr-i+1);
            st=i-dp[i];
            dr=i+dp[i];
            while (st>=1 and dr<=lg and sir[st]==sir[dr])
            {
                st--;dr++;dp[i]++;
            }
            if (dr-1>capatdr)
            {
                mij=i;capatdr=i+dp[i]-1;
            }
        }
    }
    for (int i=1;i<=lg;i++) sum=sum+dp[i]/2;
    fo<<sum;
    return 0;
}