Cod sursa(job #2023343)

Utilizator Alex18maiAlex Enache Alex18mai Data 18 septembrie 2017 19:34:10
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>

using namespace std;

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

int pali[2000100];

int main() {

    string s;
    cin>>s;
    string sir;
    for (int i=0; i<s.size(); i++){
        sir += '#';
        sir += s[i];
    }
    sir += '#';
    const int lung = sir.size();
    //cout<<sir<<'\n';
    int pos = 0;
    for (auto &x : pali){
        x++;
    }
    for (int i=1; i<lung; i++){
        int opus = pos * 2 - i;
        if (opus >= 0 && opus - pali[opus] > pos - pali[pos]){
            pali[i] = pali[opus];
            continue;
        }
        int intrare = i+1;
        if (pos + pali[pos] - 1 > i){
            intrare = pos + pali[pos];
            pali[i] += pos + pali[pos] - 1 - i;
        }
        for (int j=intrare; j<lung; j++){
            if (2 * i - j >= 0 && 2 * i - j <lung && sir[j] == sir[ 2 * i - j]){
                pali[i]++;
            }
            else{
                break;
            }
        }
        pos = i;
    }
    long long cont = 0;
    for (int i=0; i<lung; i++){
        if (sir[i + pali[i] - 1] != '#'){
            pali[i] ++;
        }
        //cout<<pali[i] / 2<<" ";
        cont += 1LL * pali[i] / 2 ;
    }
    cout<<cont;
    return 0;
}