Cod sursa(job #2023340)

Utilizator Alex18maiAlex Enache Alex18mai Data 18 septembrie 2017 19:27:06
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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;
    sir += '!';
    for (int i=0; i<s.size(); i++){
        sir += '#';
        sir += s[i];
    }
    sir +='#';
    sir += '?';
    const int lung = sir.size();
    //cout<<sir<<'\n';
    int pos = 0;
    for (int i=1; i<lung - 1; i++){
        int opus = pos * 2 - i;
        if (pos + pali[pos] > i){
            pali[i] = min(pos + pali[pos] - i , pali[opus]);
        }
        while (sir[i + pali[i] + 1] == sir[i - pali[i] - 1]){
            pali[i]++;
        }
        if (i + pali[i] > pos + pali[pos]){
            pos = i;
        }
    }
    long long cont = 0;
    for (int i=1; i<lung - 1; i++){
        //cout<<pali[i]<<" ";
        cont += 1LL * (pali[i] + 1)/ 2 ;
    }
    //cout<<'\n';
    cout<<cont;
    return 0;
}