Cod sursa(job #2415858)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 26 aprilie 2019 15:55:20
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string s, s2;
long long ans;
int dp[2000002], n;
int main()
{
    f >> s;
    n = s.size();
    string s2 = "#$";
    for(int i = 0; i < s.size(); ++i)
        s2 += s[i], s2 += '$';
    s2 += '#';
    int center = 0, right = 0, mirror = 0;
    for(int i = 1; i < s2.size() - 1; ++i)
    {
        mirror = 2 * center - i;
        if(i < right)
            dp[i] = min(dp[mirror], right - i);
        while(dp[i] < n && s2[i - dp[i] - 1] == s2[i + dp[i] + 1])
            ++dp[i];
        if(i + dp[i] > right)
            center = i, right = i + dp[i];
        ans = ans + dp[i] / 2 + dp[i] % 2;
    }
    g << ans << '\n';
    return 0;
}