Cod sursa(job #3266367)

Utilizator iccjocIoan CHELARU iccjoc Data 7 ianuarie 2025 18:54:20
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int main()
{
    string s;
    string cs;
    cin >> s;
    cs.append(1, '.');
    for(int i = 0; i < s.size(); i++)
    {
        cs.append(1, s[i]);
        cs.append(1, '.');
    }
    // for(int i = 0; i < cs.size(); i++)
    // {
    //     cout << cs[i] << " ";
    // }
    // cout << "\n";
    vector<int> man(cs.size());
    int best = 0;
    for(int i = 0; i < cs.size(); i++)
    {
        int l = 1;
        if(best + man[best]/2 >= i)
        {
            l = min(man[2 * best - i]/2, best + man[best]/2 - i) * 2 + 1;
        }
        while(i + l/2 + 1 < cs.size() && i - l/2 - 1 >= 0 && cs[i + l/2 + 1] == cs[i - l/2 - 1])
        {
            l += 2;
        }
        man[i] = l;
        if(i + l/2 > best + man[best]/2)
        {
            best = i;
        }
        // cout << man[i] << " ";
    }
    long long sum = 0;
    for(int i = 0; i < cs.size(); i++)
    {
        sum += (man[i] / 2 + 1) / 2;
    }
    cout << sum;
}