Pagini recente » Cod sursa (job #1218124) | Cod sursa (job #2222784) | Cod sursa (job #2703722) | Cod sursa (job #2623737) | Cod sursa (job #2376576)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e6 + 20;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int manacher[MAXN];
char ch[MAXN];
void bruteforce(int i,int marime){
while(ch[i + manacher[i] / 2 + 1] == ch[i - manacher[i] / 2 - 1] and i - manacher[i] / 2 - 1 >= 0 and i + manacher[i] / 2 + 1 <= marime) manacher[i] += 2;
// fout << l << " " << i << '\n';
}
///pscpld
///cabana
int main(){
ios::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
int marime = 0, best = 0;
long long maxim = 0;
char x;
for(int i = 0; i <= MAXN; ++i)
manacher[i] = 1;
while(fin.get(x) and x != '\n'){
ch[marime ++] = '*';
ch[marime ++] = x;
}
ch[marime] = '*';
for(int i = 1; i < marime; i += 1){
if(best + manacher[best] / 2 < i){
bruteforce(i, marime);
best = i;
continue;
}
manacher[i] = manacher[best - (i - best)];
if(manacher[i] >= 2 * (best + manacher[best] / 2 - i) + 1){
manacher[i] = min(manacher[i], 2 * (best + manacher[best] / 2 - i) + 1);
bruteforce(i, marime);
best = i;
}
}
for(int i = 1; i < marime; i += 1){
///fout << manacher[i] << '\n' ;
///fout << '\n' << (manacher[i] - 1) / 2;
maxim += (manacher[i] - 1) / 2;
}
fout << maxim;
return 0;
}