Pagini recente » Cod sursa (job #607687) | Cod sursa (job #2013560) | Cod sursa (job #220185) | Cod sursa (job #2010118) | Cod sursa (job #2023343)
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int pali[2000100];
int main() {
string s;
cin>>s;
string sir;
for (int i=0; i<s.size(); i++){
sir += '#';
sir += s[i];
}
sir += '#';
const int lung = sir.size();
//cout<<sir<<'\n';
int pos = 0;
for (auto &x : pali){
x++;
}
for (int i=1; i<lung; i++){
int opus = pos * 2 - i;
if (opus >= 0 && opus - pali[opus] > pos - pali[pos]){
pali[i] = pali[opus];
continue;
}
int intrare = i+1;
if (pos + pali[pos] - 1 > i){
intrare = pos + pali[pos];
pali[i] += pos + pali[pos] - 1 - i;
}
for (int j=intrare; j<lung; j++){
if (2 * i - j >= 0 && 2 * i - j <lung && sir[j] == sir[ 2 * i - j]){
pali[i]++;
}
else{
break;
}
}
pos = i;
}
long long cont = 0;
for (int i=0; i<lung; i++){
if (sir[i + pali[i] - 1] != '#'){
pali[i] ++;
}
//cout<<pali[i] / 2<<" ";
cont += 1LL * pali[i] / 2 ;
}
cout<<cont;
return 0;
}