Cod sursa(job #2973858)

Utilizator Vincent47David Malutan Vincent47 Data 2 februarie 2023 18:43:30
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <string>

using namespace std;

    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");

    const int dim = 1e5;

    long long lps(string text)
    {
        int N = text.length();

        if (!N)
        return -1;

        N = 2 * N + 1;
        int L[2 * dim + 2];
        L[0] = 0;
        L[1] = 1;

        int C = 1;
        int i = 0, R = 2, iMirror;
        int diff;
        bool expand = -1;

        for (i = 2; i < N; ++i)
        {
         iMirror = 2 * C - i;
         expand = 0;
         diff = R - i;

         if (diff >= 0)
         {
             if (L[iMirror] < diff)
                L[i] = L[iMirror];
             else if (L[iMirror] == diff && R == N - 1)
                L[i] = L[iMirror];
             else if (L[iMirror] == diff && R < N - 1)
             {
                 expand = 1;
                 L[i] = L[iMirror];
             }
             else if (L[iMirror] > diff)
             {
                 expand = 1;
                 L[i] = diff;
             }
         }
         else
         {
             L[i] = 0;
             expand = 1;
         }

         if (expand)
         {
             while (((i + L[i]) < N && (i - L[i]) > 0) && ( (i + L[i] + 1) % 2 == 0
                    || text[(i + L[i] + 1) / 2] == text[(i - L[i] - 1) / 2]) )
            L[i] ++;
         }

         if (i + L[i] > R)
         {
             C = i;
             R = i + L[i];
         }
        }

        long long ans = (N - 1) >> 1;
        for (int j = 0; j < N; ++j){
            if (L[j] > 1)
            ans += (L[j] >> 1);
        }
        return ans;
    }

int main()
{
    string s;
    cin >> s;
    cout << lps(s);
	return 0;
}