Cod sursa(job #2778222)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 30 septembrie 2021 17:11:21
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

long long count(const string &word) {
    vector<int> largestPalindrome(word.size(), 1);
    int left = 0, right = 0;
    long long answer = 0;
    for(int index = 0; index < word.size(); index ++) {
        if(index <= right) {
            largestPalindrome[index] = min(largestPalindrome[right - index + left], (right - index) * 2 + 1);
        }

        int newLeft = index - (largestPalindrome[index] / 2);
        int newRight = index + (largestPalindrome[index] / 2);
        while(newLeft - 1 >= 0 && newRight + 1 < word.size() && word[newLeft - 1] == word[newRight + 1]) {
            largestPalindrome[index] += 2;
            newLeft --;
            newRight ++;
        }
        if(newRight > right) {
            right = newRight;
            left = newLeft;
        }

        answer += (largestPalindrome[index] / 4);
    }
    return answer;

}

int main() {
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");

    string word;
    cin >> word;

    string modifiedWord = "$";
    for(char character : word) {
        modifiedWord += character;
        modifiedWord += '$';
    }

    cout << word.size() + count(modifiedWord);


    return 0;
}