Pagini recente » Cod sursa (job #1630698) | Cod sursa (job #1954253) | Cod sursa (job #114401) | Cod sursa (job #2751028) | Cod sursa (job #803340)
Cod sursa(job #803340)
#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;
s[0] = s[strlen(s + 1) + 1] = '?';
for (int i = 1 ; s[i] ; i++){
if (best + pali[best] >= i)
pali[i] = min(best + pali[best] - i, pali[2 * best - i]);
while (pali[i] < i && s[ i - pali[i] - 1 ] == s[ i + pali[i] + 1 ] )
pali[i]++;
best = i + pali[i] <= best + pali[best] ? 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;
}