Cod sursa(job #3040085)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 29 martie 2023 12:20:07
Problema PScPld Scor 0
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");
#define fin cin
#define fout cout
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]);
        }
        st = i - ans[i];
        dr = i + ans[i];
        while(s[st] == s[dr])
        {
            st--;
            dr++;
            ans[i]++;
        }



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