Cod sursa(job #2847579)

Utilizator nubnubMeh Neh nubnub Data 11 februarie 2022 00:46:30
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <vector>
#define pb push_back

using namespace std;

const int NMAX = 2000005;

string s;
vector<char>v;
long long dp[NMAX];

long long st , dr , answer , k ;

int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    cin >> s;
    int length = s.size();
    v.pb('*');
    for(int i = 0 ; i < s.size() ; i++)
    {
        v.push_back(s[i]);
        v.push_back('*');
    }
    for(int i = 0 ; i < v.size() ; i++)
    {
        if(i > dr)
            k = 0;
        else
            k = min(dp[st+dr-i],dr-i);
        while(i + k < v.size() && i - k >= 0 && v[i + k] == v[i - k])
            k++;
        dp[i] = k--;
        if(i + k > dr)
        {
            dr = i + k;
            st = i - k;
        }
    }
    answer = length;
    for(int i = 0; i < v.size(); i++)
        answer += (dp[i] - 1) / 2;
    cout << answer;
    return 0;
}