Cod sursa(job #2594080)

Utilizator ptudortudor P ptudor Data 5 aprilie 2020 13:31:59
Problema PScPld Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");
char a[1000005];
int n,p[1000005],p2[1000005];
int main()
{int i,j,Max,marg,sim;
ll s = 0;
    in >> a + 1;
    for (n = 1; a[n]; n++); n--;
    p[1] = 1, Max = 1;
    for (i = 2; i <= n; i++) {
        marg = Max + p[Max] - 1;
        if (marg <= i) {
            for (j = i + 1; a[j]  == a[i - (j - i)] && j <= n; j++); j--;
            p[i] = (j - i) + 1;
        }
        else {
            sim = Max - (i - Max);
            if (p[sim] + i - 1 < marg)
                p[i] = p[sim];
            else {
                for (j = marg; a[j]  == a[i - (j - i)] && j <= n; j++); j--;
                p[i] = (j - i) + 1;
            }
        }

        if (p[i] + i - 1 > p[Max] + Max - 1) Max = i;
    }


    if (a[1] == a[2]) p2[1] = 1, Max = 1;
    Max = 0;
    for (i = 2; i <= n; i++) {
        marg = Max + p[Max];
        if (a[i] != a[i + 1]) {
            p2[i] = 0;
            continue;
        }
        if (marg <= i) {
            for (j = i + 2; a[j]  == a[i - (j - i) + 1] && j <= n; j++); j--;
            p2[i] = (j - i);
        }
        else {
            sim = Max - (i - Max);
            if (p2[sim] + i < marg)
                p2[i] = p2[sim];
            else {
                for (j = marg; a[j]  == a[i - (j - i) + 1] && j <= n; j++); j--;
                p2[i] = (j - i);
            }
        }

        if (p2[i] + i > p2[Max] + Max) Max = i;
    }
    for (i = 1; i <= n; i++) s += p[i] + p2[i];
   /* for (i = 1; i <= n; i++) cout << a[i] << " " ; cout << "\n";
    for (i = 1; i <= n; i++) cout << p[i] << " " ; cout << "\n";
    for (i = 1; i <= n; i++) cout << p2[i] << " " ; cout << "\n";*/

    out << s << "\n";
    out.close();
    in.close();
    return 0;
}