Cod sursa(job #2260563)

Utilizator mircearoataMircea Roata Palade mircearoata Data 15 octombrie 2018 09:58:06
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

vector<char> v;
char ch[1000001];
long long cnt[2000001];
long long n, l, r, k;
long long ans;

int main()
{
    in >> ch;
    n = strlen(ch);
    for(int i = 0; i < n; i++)
    {
        v.push_back('*');
        v.push_back(ch[i]);
    }
    v.push_back('*');
    for(int i = 0; i < (int)v.size(); i++)
    {
        if(i > r)
            k = 0;
        else
            k = min(cnt[l+r-i], r-i);
        while(i + k < (int)v.size() && i - k >= 0 && v[i + k] == v[i - k])
            k++;
        cnt[i] = k--;
        if(i + k > r)
        {
            r = i + k;
            l = i - k;
        }
    }
    ans = n;
    for(int i = 0; i < (int)v.size(); i++)
        ans += (cnt[i] - 1) / 2;
    out << ans;
    return 0;
}