Cod sursa(job #2528386)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 21 ianuarie 2020 20:16:38
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>
#define NMAX (int)(1e5+4)
#define pb push_back
#define ft first
#define sd second
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
typedef pair <int, int> pairINT;
typedef long long ll;

int n,c,r,sol,dp[NMAX];
string s;

int main(){
    fin>>s;
    n=s.size()*2-1;
    for(int i=0;i<n;++i){
        if (2*r >= i)
            dp[i]=dp[2*c-i];
        else dp[i]=-i%2;
        while (i - 2 * (dp[i] + 1) >= 0 && s[(i - 2 * (dp[i] + 1)) / 2] == s[(i + 2 * (dp[i] + 1) + 1) / 2])
            ++dp[i];
        
        if ((i + 2 * dp[i] + 1) / 2 > r){
            r = (i + 2 * dp[i] + 1) / 2;
            c = i;
        }

        sol += dp[i] + 1;
    }
    fout<<sol;
    return 0;
}