Cod sursa(job #3129251)

Utilizator user12345user user user user12345 Data 13 mai 2023 15:43:18
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

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

char s[1000005];
int last1[1000005], last2[1000005], n;

int main() {

    fin >> (s + 1);

    n = strlen(s + 1);
    s[0] = '~';
    s[n + 1] = '/';

    last1[1] = 1;
    last2[n] = 1;

    for (int i = 2; i <= n; i++)
        if (s[i] == s[i - 1])
            last1[i] = 1 + last1[i - 1];
        else
            last1[i] = 1;

    for (int i = n - 1; i >= 1; i--)
        if (s[i] == s[i + 1])
            last2[i] = last2[i + 1] + 1;
        else
            last2[i] = 1;

    long long res = 0;

    for (int i = 1; i <= n; i++) {

        int l = i - 1, r = i + 1;

        while (s[l] == s[r] && last1[l] == last2[r]) {

            l -= last1[l];
            r += last2[r];
        }

        if (s[l] == s[r]) {

            int aux = min(last1[l], last2[r]);
            l -= aux;
            r += aux;
        }

        if (s[l] != s[r]) {

            l++;
            r--;
        }

        res += (i - l + 1);
    }

    for (int i = 1; i < n; i++) {

        if (s[i] != s[i + 1])
            continue;

        int l = i, r = i + 1;

        while (s[l] == s[r] && last1[l] == last2[r]) {

            l -= last1[l];
            r += last2[r];
        }

        if (s[l] == s[r]) {

            int aux = min(last1[l], last2[r]);
            l -= aux;
            r += aux;
        }

        if (s[l] != s[r]) {

            l++;
            r--;
        }
        res += (i - l + 1);
    }

    fout << res;

    return 0;
}