Cod sursa(job #2456075)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 13 septembrie 2019 14:38:38
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

char s[1000005], t[2000005];
ll n, c, r, q[2000005], nr, ans;

int main()
{
    fin >> s+1;
    for(int i = 1; i <= strlen(s+1); i++)
    {
        t[nr] = '$';
        nr++;
        t[nr] = s[i];
        nr++;
    }
    t[nr]   = '$';
    c = 1;
    q[1] = 1;
    r = 2;
    ans = 1;
    for(int i = 2; i <= nr; i++)
    {
        if(i<r)
        q[i] = min(q[2*c-i], r-i);
       ll a, b;
       a = i-q[i];
       b = i+q[i];
       while(a-1>=0 &&  b+1<= nr && t[a-1] == t[b+1])
       {
           a--;
           b++;
       }
       if(b > r)
       {
          r = b;
          c = i;
       }
       q[i] = b-i;
       ans += q[i]/2+q[i]%2;

    }

    fout << ans;
    return 0;
}