Cod sursa(job #2701218)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 30 ianuarie 2021 10:25:42
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");

int main(){
    std::string s, x = "#";
    fin >> s;

    for(int i=0; i<s.size(); i++){
        x.push_back(s[i]);
        x.push_back('#');
    }

    int lps[x.size()] = {};
    lps[0] = 1;

    int left=0, right=-1;

    for(int i=1, k; i<x.size(); i++){
        if(right >= i) k = std::min(lps[left + (right - i)], right - i + 1);
        else k = 1;

        while(0 <= i - k and i + k < x.size() and x[i-k] == x[i+k])
            k ++;

        lps[i] = k--;
        if(i + k  > right){
            right = i + k;
            left = i - k;
        }
    }

    int ans = 0;

    for(int i=0; i<x.size(); i++)
        ans = ans + lps[i] / 2;
    fout << ans << '\n';

    return 0;
}