Cod sursa(job #2528427)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 21 ianuarie 2020 21:01:21
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
#define NMAX (int)(2e6+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,dp[NMAX];
ll sol;
string s;

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

        while (i - 2 * dp[i] >= 0 && i + 2 * dp[i] + 1 <= n && s[(i - 2 * dp[i]) / 2] == s[(i + 2 * dp[i] + 1)/2])
            ++dp[i];
        if(i+2 * dp[i] + 1 > r)
            c = i,
            r = i + 2 * dp[i];
         sol += dp[i];
    }
    fout<<sol;
    return 0;
}