Pagini recente » Istoria paginii utilizator/popavlad | Diferente pentru rotatie-lexicografic-minima intre reviziile 32 si 33 | Cod sursa (job #1256751) | Clasament dupa rating | Cod sursa (job #2023339)
#include <fstream>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
long long pali[2000100];
int main() {
string s;
cin>>s;
string sir;
sir += '!';
for (long long i=0; i<s.size(); i++){
sir += '#';
sir += s[i];
}
sir +='#';
sir += '?';
const long long lung = sir.size();
//cout<<sir<<'\n';
long long pos = 0;
for (long long i=1; i<lung - 1; i++){
long long 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 (long long i=1; i<lung - 1; i++){
//cout<<pali[i]<<" ";
cont += (pali[i] + 1)/ 2 ;
}
//cout<<'\n';
cout<<cont;
return 0;
}