Pagini recente » Cod sursa (job #1944973) | Cod sursa (job #320542) | Cod sursa (job #55128) | Cod sursa (job #1398461) | Cod sursa (job #973267)
Cod sursa(job #973267)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int Nmax = 1000005;
int N; char S[Nmax]; int Sol[2 * Nmax]; int X[2 * Nmax];
void Read() {
fin >> S + 1;
N = strlen(S + 1);
for(int i = 1; i <= N; ++i)
X[2 * i] = S[i] - 'a' + 1;
N = 2 * N + 1; X[0] = -1; X[N + 1] = -2;
}
void Solve() {
int Center = -1000; int Right = -1000;
for(int i = 1; i <= N; ++i) {
int St = i, Dr = i;
if(i > Right)
Sol[i] = 0;
else {
int Radius = i - Center;
Sol[i] = Sol[Center - Radius];
if(Sol[i] + i > Right)
Sol[i] = Right - i;
St = St - Sol[i]; Dr = Dr + Sol[i];
}
while(X[St - 1] == X[Dr + 1]){
--St; ++Dr; ++Sol[i];
}
if(Dr > Right){
Right = Dr; Center = i;
}
}
}
int main() {
Read();
Solve();
long long Solution = 0;
for(int i = 1; i <= N; ++i)
Solution += (Sol[i] + 1) / 2;
fout << Solution <<'\n';
return 0;
}