Cod sursa(job #2262529)

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