Cod sursa(job #2713529)

Utilizator AACthAirinei Andrei Cristian AACth Data 28 februarie 2021 10:55:24
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int Max = 1e6 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
char s[Max];
char sir[2*Max];
void read()
{
    f.get(s,Max);
    int i;
    int it = -1;
    for(i=0; s[i]; i++)
    {
        sir[++it] = s[i];
        sir[++it] = '#';
    }
}
int dp[2*Max];
void solve()
{
    int has_pair = -1;
    int pair_center;
    int i;
    int last = strlen(sir);
    last --;
    for(i=0; sir[i]; i++)
    {
        int j;
        if(has_pair > i)
        {
            int delta = has_pair - pair_center;
            j = dp[pair_center - delta];
            dp[i] = j;
        }
        else
            j = 0;

        while(i - j >=0 and i+j <= last and sir[i-j] == sir[i+j])
        {
            dp[i] ++;
            ++j;
        }
        if(i+j - 1 > has_pair)
        {
            has_pair = i + j - 1;
            pair_center = i;
        }
    }
    int ans = 0;
//    for(i=0; sir[i]; i++)
//        cout<<sir[i]<<' ';
//    cout<<'\n';
//    for(i=0; sir[i]; i++)
//        cout<<dp[i]<<' ';
//    cout<<'\n';
     for(i=0; sir[i]; i++)
     {
         if(sir[i] == '#')
         {
             int sir_max = dp[i] -1;
             int last = sir_max / 2;
             ans += last;
         }
         else
         {
            int last = dp[i] + 1;
            last /= 2;
            ans += last;
         }
     }

    g<<ans;
}
void restart()
{

}

int32_t main()
{
    nos();
    read();
    solve();
    restart();

    return 0;
}