Pagini recente » Cod sursa (job #1943871) | Cod sursa (job #1722279) | Cod sursa (job #2323175) | Cod sursa (job #422809) | Cod sursa (job #2289970)
#include <bits/stdc++.h>
#define ll long long
#define maxN 100000
using namespace std;
FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);
char s[maxN + 1];
class String
{
public :
int n, *p;
char *Q;
String(int n)
{
this->n = n;
p = new int[2 * n + 1];
Q = new char[2 * n + 1];
Q[0] = '@';
Q[2 * n] = '$';
for (int i = 0; i <= 2 * n; ++ i)
p[i] = 0;
for (int i = 1; i < 2 * n; ++ i)
if (i & 1)
Q[i] = s[i / 2];
else
Q[i] = '#';
}
void compP();
};
ll ans;
void String::compP()
{
int N = 2 * n;
int c = 0, r = 0;
for (int i = 1; i < N; ++ i)
{
int iMirror = 2 * c - i;
if (r > i)
p[i] = min(p[iMirror], r - i);
while (Q[i + p[i] + 1] == Q[i - p[i] - 1])
++ p[i];
if (p[i] + i > r)
{
c = i;
r = i + p[i];
}
ans += (p[i] / 2);
}
}
int main()
{
scanf("%s", &s);
int n = strlen(s);
String S(n);
S.compP();
printf("%lld\n", ans + n);
return 0;
}