Cod sursa(job #2699327)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 24 ianuarie 2021 10:47:03
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <bitset>
#include <queue>

#define maxn 100005
#define maxv 1005
#define mod 998244353LL

// #define fin std::cin
// #define fout std::cout

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



int32_t main(){
    std::string s="#", x;
    fin >> x;
    for(char chr: x){
        s.push_back(chr);
        s.push_back('#');
    }

    int lps[s.size()] = {};
    int left, right = -1;
    for(int i=1; i<s.size(); i++){
        int k = 1;
        if(right >= i) k = std::min(lps[left + right - i], right - i + 1);
        while(i-k >= 0 and i+k < s.size() and s[i-k] == s[i+k])
            k ++;

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

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


    return 0;
}