Pagini recente » Cod sursa (job #3221) | Cod sursa (job #3221907) | Cod sursa (job #2558488) | Cod sursa (job #2927925) | Cod sursa (job #3294660)
#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;
}
answer += len[i] / 2 + (s[i] != '#');
}
fout << answer << "\n";
return 0;
}