Cod sursa(job #1823031)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 5 decembrie 2016 20:09:55
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

class Manacher {
    public:
        explicit Manacher(const string& text) {
            text_ = "$";
            for (auto ch : text) {
                text_ += ch;
                text_ += '$';
            }

            longest_ = vector<int>(text_.size());
            for (int i = 0; i < (int)text_.size(); i++) {
                longest_[i] = (text_[i] != '$');
            }
        }

        void Prepare() {
            int center = 0;
            int max_right = 0;

            for (int i = 1; i < (int)text_.size(); i++) {
                int mirror = 2 * center - i;

                if (i <= max_right) {
                    longest_[i] = min(longest_[mirror], max_right - i + 1);
                }

                int left = i - longest_[i] + 1;
                int right = i + longest_[i] - 1;
                while (left - 2 >= 0 && right + 2 < (int)text_.size()
                        && text_[left - 2] == text_[right + 2]) {
                    left -= 2;
                    right += 2;
                    longest_[i] += 2;
                }

                if (right > max_right) {
                    max_right = right;
                    center = i;
                }
            }
        }

        long long GetNumberOfPalindromes() const {
            long long palindromes = 0;
            for (int i = 0; i < (int)longest_.size(); i++) {
                palindromes += (longest_[i] + 1) / 2;
            }
            return palindromes;
        }

    private:
        string text_;
        vector<int> longest_;
};

int main() {
    cin.sync_with_stdio(false);

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

    string s;
    cin >> s;

    Manacher manacher(s);
    manacher.Prepare();
    cout << manacher.GetNumberOfPalindromes() << '\n';

    return 0;
}