Cod sursa(job #3040086)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 29 martie 2023 12:21:00
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;
string s, a;
int ans[1000001], st, dr, mij, sum;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
    fin >> a;
    s += '!';
    for(int i = 0; i  < a.size(); ++ i)
    {
        s += a[i];
        s += '!';
    }
    st = 0;
    dr = 0 ;
    for(int i = 1; i < s.size(); ++ i)
    {
        if(i < dr)
        {
            ans[i] = min(dr - i, ans[st + dr - i]);
        }
        while(s[i - ans[i]] == s[i + ans[i]])
        {
            ans[i]++;
        }
        if(i + ans[i]> dr)
        {
            dr = i + ans[i];
            st = i - ans[i];
        }



    }
    for(int i = 0; i < s.size(); i ++)
        sum += ans[i] / 2;
    fout << sum;
    return 0;
}