Cod sursa(job #1969860)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 18 aprilie 2017 18:03:20
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
/**
  *  Worg
  */
#include <cstdio>
#include <cstring>
#include <algorithm>

FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);

const int kMaxN = 1 + 1000000;

/*-------- Data --------*/
int N;
char initial[kMaxN], transformed[kMaxN * 2 + 5];

int len[kMaxN * 2 + 5];
/*-------- --------*/

void GetTransformed() {
    for(int i = 1; i <= N; i++) {
		transformed[i << 1] = initial[i];
    }
    N = (N << 1) + 1;
    for(int i = 1; i <= N; i += 2) {  //  Pe pozitii impare punem caractere speciale
		transformed[i] = '$';
    }
}

long long ManacherAlgorithm(char *s, const int N) {
	long long answer = 0;
	int index = 0, center = 0;
    for(int i = 1; i <= N; i++) {
		if(i <= index) {
			len[i] = std::min(index - i + 1, len[center - (i - center)]);
		}
		while(i - len[i] >= 1 && i + len[i] <= N && s[i + len[i]] == s[i - len[i]]) {
			len[i] ++;
		}
		answer += len[i] / 2;
		if(i + len[i] - 1 > index) {
			index = i + len[i] - 1;
			center = i;
		}
    }
    return answer;
}

int main() {
    scanf("%s", initial + 1); N = std::strlen(initial + 1);
    GetTransformed();
    printf("%lld\n", ManacherAlgorithm(transformed, N));
    return 0;
}