Pagini recente » Cod sursa (job #1623185) | Cod sursa (job #235562) | Arhiva de probleme | Cod sursa (job #362760) | Cod sursa (job #842263)
Cod sursa(job #842263)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 1000005;
int P[N];
char s[N];
ifstream in("pscpld.in");
ofstream out("pscpld.out");
long long pali(char s[], bool d){
int best = 0;
long long rez = 0;
memset(P, 0, sizeof(P));
char *a = s, *b = s + 1 - d;
for (int i = 1 ; s[i] ; i++){
if (i < best + P[best])
P[i] = min(best + P[best] - i, P[2 * best - i]);
while (P[i] < i && b[ i + P[i]] && a[i - P[i]] == b[i + P[i]])
P[i]++;
if (i + P[i] > best + P[best])
best = i;
rez += P[i];
}
return rez;
}
int main(){
in >> (s + 1);
out << pali(s, 0) + pali(s, 1) << "\n";
return 0;
}