Pagini recente » Cod sursa (job #2401909) | Cod sursa (job #1551732) | Cod sursa (job #605564) | Cod sursa (job #1623449) | Cod sursa (job #2594080)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
char a[1000005];
int n,p[1000005],p2[1000005];
int main()
{int i,j,Max,marg,sim;
ll s = 0;
in >> a + 1;
for (n = 1; a[n]; n++); n--;
p[1] = 1, Max = 1;
for (i = 2; i <= n; i++) {
marg = Max + p[Max] - 1;
if (marg <= i) {
for (j = i + 1; a[j] == a[i - (j - i)] && j <= n; j++); j--;
p[i] = (j - i) + 1;
}
else {
sim = Max - (i - Max);
if (p[sim] + i - 1 < marg)
p[i] = p[sim];
else {
for (j = marg; a[j] == a[i - (j - i)] && j <= n; j++); j--;
p[i] = (j - i) + 1;
}
}
if (p[i] + i - 1 > p[Max] + Max - 1) Max = i;
}
if (a[1] == a[2]) p2[1] = 1, Max = 1;
Max = 0;
for (i = 2; i <= n; i++) {
marg = Max + p[Max];
if (a[i] != a[i + 1]) {
p2[i] = 0;
continue;
}
if (marg <= i) {
for (j = i + 2; a[j] == a[i - (j - i) + 1] && j <= n; j++); j--;
p2[i] = (j - i);
}
else {
sim = Max - (i - Max);
if (p2[sim] + i < marg)
p2[i] = p2[sim];
else {
for (j = marg; a[j] == a[i - (j - i) + 1] && j <= n; j++); j--;
p2[i] = (j - i);
}
}
if (p2[i] + i > p2[Max] + Max) Max = i;
}
for (i = 1; i <= n; i++) s += p[i] + p2[i];
/* for (i = 1; i <= n; i++) cout << a[i] << " " ; cout << "\n";
for (i = 1; i <= n; i++) cout << p[i] << " " ; cout << "\n";
for (i = 1; i <= n; i++) cout << p2[i] << " " ; cout << "\n";*/
out << s << "\n";
out.close();
in.close();
return 0;
}