Pagini recente » Cod sursa (job #382123) | Cod sursa (job #1047931) | Cod sursa (job #2751255) | Cod sursa (job #1771241) | Cod sursa (job #803325)
Cod sursa(job #803325)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 2000005;
int pali[N];
char s[N];
ifstream in("pscpld.in");
ofstream out("pscpld.out");
void stretch(char* s){
for (int i = 2 * strlen(s + 1) - 1 ; i ; i--)
if (i & 1)
s[i] = s[ (i + 1) >> 1];
else
s[i] = '#';
}
void manacher(char* s){
int best = 0;
for (int i = 1 ; s[i] ; i++){
if (best + pali[best] >= i)
pali[i] = min(best + pali[best], i + pali[2 * i - best]) - i;
while (pali[i] < i && s[ i - pali[i] - 1 ] == s[ i + pali[i] + 1 ] )
pali[i]++;
best = best + pali[best] > i + pali[i] ? best : i;
}
}
int main(){
in.getline(s + 1, N);
stretch(s);
manacher(s);
int rez = 0;
for (int i = 1 ; s[i] ; i++)
rez += (pali[i] + 1 + (i & 1)) >> 1;
out << rez << "\n";
return 0;
}