Pagini recente » Profil shaghi | Monitorul de evaluare | Clasament dupa rating | Istoria paginii utilizator/iuliaiulia1999 | Cod sursa (job #2023340)
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int pali[2000100];
int main() {
string s;
cin>>s;
string sir;
sir += '!';
for (int i=0; i<s.size(); i++){
sir += '#';
sir += s[i];
}
sir +='#';
sir += '?';
const int lung = sir.size();
//cout<<sir<<'\n';
int pos = 0;
for (int i=1; i<lung - 1; i++){
int opus = pos * 2 - i;
if (pos + pali[pos] > i){
pali[i] = min(pos + pali[pos] - i , pali[opus]);
}
while (sir[i + pali[i] + 1] == sir[i - pali[i] - 1]){
pali[i]++;
}
if (i + pali[i] > pos + pali[pos]){
pos = i;
}
}
long long cont = 0;
for (int i=1; i<lung - 1; i++){
//cout<<pali[i]<<" ";
cont += 1LL * (pali[i] + 1)/ 2 ;
}
//cout<<'\n';
cout<<cont;
return 0;
}