Cod sursa(job #2713552)

Utilizator AACthAirinei Andrei Cristian AACth Data 28 februarie 2021 11:12:11
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 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]="";
int n;
void read()
{
    f>>s;
    int i;
    int it = -1;
    for(i=0; s[i]; i++)
    {
        sir[++it] = '#';
        sir[++it] = s[i];
    }
    sir[++it] = '#';
    n = it;
}
int dp[2*Max];
void solve()
{
    int left ;
    int right = -1;
    int i;
    int last = n;

    for(i=0; i<=n; i++)
    {
        int j;
        if(right >= i)
            j = min(dp[left + right - i],right - i + 1);
        else
            j = 1;

        while(i - j >=0 and i+j <= last and sir[i-j] == sir[i+j])
            ++j;
        dp[i] = j;
        if(i+j - 1 > right)
        {
            right = i + j - 1;
            left = i - j + 1;
        }
    }
    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; i<=n; i++)
         ans+= dp[i] / 2;


    g<<ans;
}
void restart()
{

}

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

    return 0;
}