Pagini recente » Cod sursa (job #2613489) | Cod sursa (job #67379) | Diferente pentru implica-te/arhiva-educationala intre reviziile 207 si 208 | Cod sursa (job #198122) | Cod sursa (job #3294661)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int MAXN = 1000000;
int len[2 * MAXN + 1];
int main() {
string s;
fin >> s;
string t = "#";
for(int i = 0; i < (int)s.size(); i++) {
t.push_back(s[i]);
t.push_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;
}
answer += len[i] / 2 + (s[i] != '#');
}
fout << answer << "\n";
return 0;
}