Pagini recente » Cod sursa (job #2751101) | Cod sursa (job #3291564) | Cod sursa (job #3291534) | Cod sursa (job #1958901) | Cod sursa (job #3294662)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int MAXN = 1000000;
int len[2 * MAXN];
int main() {
string s;
fin >> s;
string t = "";
for(int i = 0; i < (int)s.size() - 1; i++) {
t.push_back(s[i]);
t.push_back('#');
}
t.push_back(s.back());
s = t;
int center = 0, maxr = -1;
long long answer = 0;
for(int i = 0; i < (int)s.size(); i++) {
if(center < i && i < maxr) {
int mirror = 2 * center - i; // oglinda in cealalta jumatate
// se copiaza palindromul centrat in mirror invers la i
len[i] = min(len[mirror], maxr - i);
} else {
len[i] = 0;
}
while(i - len[i] - 1 >= 0 && i + len[i] + 1 < (int)s.size() &&
s[i - len[i] - 1] == s[i + len[i] + 1]) {
len[i]++;
}
if(i + len[i] > maxr) {
maxr = i + len[i];
center = i;
}
if(s[i] == '#') {
answer += (len[i] + 1) / 2;
} else {
answer += len[i] / 2 + 1;
}
}
fout << answer << "\n";
return 0;
}