Cod sursa(job #3040117)

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

using namespace std;
string s, a;
int ans[2000001], st, dr, mij;
long long 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 = -1;
    dr = -1 ;
    for(int i = 1; i < s.size(); ++ i)
    {
        if(i <= dr)
        {
            ans[i] = min(dr - i, ans[st + dr - i]);
        }
        else
            ans[i] = 0;
        while(i - ans[i] >= 0 && s[i - ans[i]] == s[i + ans[i]])
        {
            ans[i]++;
        }
        if(i + ans[i] - 1 > dr)
        {
            dr = i + ans[i] - 1;
            st = i - ans[i] + 1;
        }
    }
    for(int i = 0; i < s.size(); i ++)
        sum += ans[i] / 2;
    fout << sum;
    return 0;
}