Cod sursa(job #2190709)

Utilizator mihai.alphamihai craciun mihai.alpha Data 31 martie 2018 16:16:58
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
#include <cctype>
#include <algorithm>

const int maxn = 1000005;

char s[maxn + 5], a[2 * maxn + 5];
int l[maxn * 2 + 5];
FILE *fin, *fout;
int n, m;

int main()  {
    fin = fopen("pscpld.in", "r");
    fout = fopen("pscpld.out", "w");
    fgets(s + 1, maxn, fin);
    n = 0, m = 0;
    for(int i = 1;isalpha(s[i]);i++)
        n = i;
    m = n * 2 + 1;
    for(int i = 1;i <= n;i++)
        a[i * 2 - 1] = '*', a[i * 2] = s[i];
    a[2 * n + 1] = '*';
    int id = 0;
    long long ans = 0LL;
    for(int i = 1;i <= m;i++)  {
        if(id + l[id] > i)
            l[i] = std::min(l[2 * id - i], id + l[id] - i);
        else
            l[i] = 1;
        while(i > l[i] && a[i - l[i]] == a[i + l[i]])
            l[i]++;
        ans += 1LL * l[i] / 2;
        if(i + l[i]  > id + l[id])
            id = i;
    }
    fprintf(fout, "%lld", ans);
    fclose(fin);
    fclose(fout);
	return 0;
}