Cod sursa(job #2590802)

Utilizator vladth11Vlad Haivas vladth11 Data 28 martie 2020 22:11:33
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;
typedef long long ll;

int p[2000005];
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
ll Manacher(string s)
{
    ll rez = 0;
    int lg = s.size();
    int l = 0,r = -1;
    for(int i = 0; i < lg; i++)
    {
        int k = 0;
        if(i > r)
        {
            k = 1;
        }
        else
        {
            k = min(p[r - i + l], r - i + 1);
        }
        while(i - k >= 0 && i + k < lg && s[i - k] == s[i + k])
            k++;
        k--;
        p[i] = k;
        if(i + k > r)
        {
            r = i + k;
            l = i - k;
        }
        rez += 1LL * (p[i] + 1) / 2;
    }


    return rez;
}

int main()
{
    int i;
    InParser cin("pscpld.in");
    ofstream cout("pscpld.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string a,s = "";
    cin >> a;
    s += "#";
    for(i = 0; i < a.size(); i++)
    {
        s += a[i];
        s += "#";
    }
    cout << Manacher(s);
    return 0;
}