Cod sursa(job #1818492)

Utilizator AndreiFlorescuAndrei Florescu AndreiFlorescu Data 29 noiembrie 2016 12:41:24
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 2000010;

int n, m, i, a[N], mij, sim;
char s[N], v[N];
long long sol;

int main () {
    fin >> (s + 1);
    n = strlen(s + 1);
    for (i = 1; i <= n; ++i) {
        v[++m] = ' ';
        v[++m] = s[i];
    }
    v[++m] = ' ';
    for (i = 1; i <= m; ++i) {
        /*if (i <= mij + a[mij] - 1) {
            sim = (mij << 1) - i;
            a[i] = min(a[sim], mij + a[mij] - i);
        }*/
        while (v[i + a[i]] && v[i + a[i]] == v[i - a[i]])
            a[i]++;
        /*if (i + a[i] > mij + a[mij])
            mij = i;*/
        sol += a[i] / 2;
    }
    fout << sol << "\n";
    return 0;
}