Pagini recente » Cod sursa (job #2641917) | Cod sursa (job #2113849) | Cod sursa (job #2980200) | Cod sursa (job #2174435) | Cod sursa (job #2592175)
#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 1000000;
int manacher[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;
string s = "&#";
char ch;
while ( isalpha( ch = fgetc( fin ) ) ) {
s += ch;
s += '#';
}
s += "%";
n = s.size();
for ( i = 2; i < n; i ++ ) {
if ( poz + length_so_far < i ) {
st = i - 1;
dr = i + 1;
length = 0;
while ( s[st] == s[dr] ) {
st --;
dr ++;
length ++;
}
manacher[i] = length;
} else {
manacher[i] = min( poz + length_so_far - i, manacher[poz - ( i - poz )] );
st = i - manacher[i] - 1;
dr = i + manacher[i] + 1;
while ( s[st] == s[dr] ) {
st --;
dr ++;
manacher[i] ++;
}
}
if ( manacher[i] + i >= length_so_far + poz ) {
length_so_far = manacher[i];
poz = i;
}
}
long long palindrome = 0;
for ( i = 2; i < n; i ++ ) {
if ( s[i] != '#' ) {
palindrome += manacher[i] / 2;
} else {
palindrome += manacher[i] / 2 + 1;
}
}
fout << palindrome;
return 0;
}