Pagini recente » Cod sursa (job #1006329) | Cod sursa (job #2277040) | Cod sursa (job #227036) | Cod sursa (job #2397532) | Cod sursa (job #842255)
Cod sursa(job #842255)
#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));
d = !d;
for (int i = 1 ; s[i] ; i++){
if (i < best + P[best])
P[i] = min(best + P[best] - i - 1, P[2 * best - i + d]);
while (P[i] < i && s[ i + P[i] + d] && s[i - P[i]] == s[i + P[i] + d])
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;
}