Pagini recente » Cod sursa (job #1540347) | Cod sursa (job #478723) | Cod sursa (job #774292) | Cod sursa (job #2549117) | Cod sursa (job #2089448)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int const nmax = (int) 1e6;
char sir[2 * nmax + 2];
int dp[2 * nmax + 1];
int n;
long long nr;
int main() {
in >> sir;
n = strlen(sir);
for(int i = n - 1; i >= 0; i--) {
sir[2 * i + 1] = sir[i];
sir[2 * i + 2] = '*';
}
sir[0] = '*';
sir[2 * n] = '*';
n = 2 * n;
//cout << sir;
int c = 1;
int dr = c;
for(int i = 0; i <= n; i++) {
if(i < dr)
dp[i] = min(dp[2 * c - i], dr - i);
else
dp[i] = 1;
while(sir[i - dp[i]] == sir[i + dp[i]])
dp[i]++;
if(dr < i + dp[i]) {
c = i;
dr = i + dp[i];
}
nr += 1LL * (dp[i] / 2);
}
out << nr << '\n';
in.close();
out.close();
return 0;
}