Cod sursa(job #3004931)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 16 martie 2023 18:08:38
Problema PScPld Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <string>

using namespace std;

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

const int N = 1000000;
int ans[N];

string str;

int manacher ( ) {
    
    int mij = 0, dr = 0;
    
    for ( int i = 1; i < str.size(); i++ ) {
        
        ans[i] = 0;
        
        if(i <= dr)
            ans[i] = min ( ans[2 * mij - i], dr - i );
        
        if(i + ans[i] >= dr) {
            
            mij = i;
            
            while(str[i + ans[i] + 1] == str[i - ans[i] - 1])
                ans[i]++;
            
            dr = i + ans[i];
        }
    }

    return 0;
}

int main() {
    
    ios_base::sync_with_stdio(false);
    fin.tie(0);

    char chr;
    
    str = "#*";
    
    while(fin >> chr) {
        str += chr;
        str += '*';
    }
    
    str += '$';

    manacher ();

    long long int cnt = str.size() / 2 - 1;
    
    for ( int i = 0; i < str.size(); i++ )
        cnt += ans[i] / 2;
    
    fout << cnt << '\n';
}