Pagini recente » Cod sursa (job #2736418) | Cod sursa (job #79157) | Cod sursa (job #1143188) | Cod sursa (job #1538375) | Cod sursa (job #2999841)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMAX = 1e6;
string s;
int pal[2 * NMAX + 1];
int main() {
char ch;
while(fin >> ch) {
s.push_back('$');
s.push_back(ch);
}
s.push_back('$');
for(int i = 0, st = 0, dr = 0; i < (int) s.size(); i++) {
if(i < dr) {
pal[i] = min(dr - i + 1, pal[st + dr - i]);
}
while(i - pal[i] >= 0 && i + pal[i] < (int) s.size() && s[i - pal[i]] == s[i + pal[i]]) {
pal[i]++;
}
if(i + pal[i] - 1 > dr) {
dr = i + pal[i] - 1;
st = i - pal[i] + 1;
}
}
// cout << s << '\n';
// for(int i = 0; i < (int) s.size(); i++) {
// cout << pal[i];
// }
// cout << '\n';
long long ans = 0;
for(int i = 0; i < (int) s.size(); i++) {
ans += pal[i] / 2;
}
fout << ans << '\n';
return 0;
}