Pagini recente » Cod sursa (job #2798325) | Cod sursa (job #1499906) | Cod sursa (job #434111) | Cod sursa (job #2770142) | Cod sursa (job #2592201)
///Tudy & Cal
#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 1000000;
int manacher[2 * NMAX + 3];
char s[2 * NMAX + 3];
int main() {
FILE *fin = fopen( "pscpld.in", "r" );
ofstream fout( "pscpld.out" );
int i, n, length_so_far = 0, poz = 0, st, dr, length;
s[0] = '&';
s[1] = '#';
n = 2;
char ch;
while ( ( ch = fgetc( fin ) ) != '\n' ) {
s[n++] = ch;
s[n++] = '#';
}
s[n++] = '%';
long long palindrome = 0;
for ( i = 2; i < n - 1; i ++ ) {
if ( poz + length_so_far < i ) {
st = i - 1;
dr = i + 1;
length = 0;
while ( s[st] == s[dr] ) {
st --;
dr ++;
length ++;
}
} else {
manacher[i] = min ( poz + length_so_far - i, manacher[poz - ( i - poz )] );
st = i - manacher[i] - 1;
dr = i + manacher[i] + 1;
length = manacher[i];
while ( s[st] == s[dr] ) {
st --;
dr ++;
length ++;
}
}
manacher[i] = length;
if ( manacher[i] + i >= length_so_far + poz ) {
length_so_far = manacher[i];
poz = i;
}
palindrome += manacher[i] / 2 + i % 2;
}
fout << palindrome;
return 0;