Cod sursa(job #3129254)

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

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

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

int main() {

    fin >> s;

    n = s.length();
    s = '~' + s;
    s = s + '/';

    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;
}