Pagini recente » Cod sursa (job #2714399) | Borderou de evaluare (job #2457944) | Cod sursa (job #2458009)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int n;
long long ans;
int v[2000010];
char a[2000010];
string s;
int main() {
fin >> s;
a[++n] = '@';
a[++n] = s[0];
for (int i = 1; i < s.size(); ++i) {
a[++n] = '*';
a[++n] = s[i];
}
a[++n] = '#';
int l = 1, r = 1, mij = 1;
for (int i = 2; i < n; ++i) {
if (i < r) {
if (v[mij - (i - mij)] + i < r)
v[i] = v[mij - (i - mij)];
else {
int x = min(v[mij - i + mij] + 1, n - i);
while (a[i + x] == a[i - x])
++x;
while (a[i + x] != a[i - x])
--x;
if (i + x > r)
r = i + x, mij = i;
v[i] = x;
}
} else {
int x = 1;
while (a[i + x] == a[i - x])
++x;
while (a[i + x] != a[i - x])
--x;
r = i + x, mij = i;
v[i] = x;
}
if (a[i] == '*')
ans += ((long long)v[i] + 1) / 2;
else
ans += ((long long)v[i] / 2) + 1;
}
fout << ans;
// for (int i = 1; i <= n; ++i)
// fout << a[i] << ' ';
// fout << '\n';
// for (int i = 1; i <= n; ++i)
// fout << v[i] << ' ';
return 0;
}