Pagini recente » Cod sursa (job #538251) | Cod sursa (job #1996062) | Cod sursa (job #656901) | Cod sursa (job #1677047) | Cod sursa (job #2973858)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int dim = 1e5;
long long lps(string text)
{
int N = text.length();
if (!N)
return -1;
N = 2 * N + 1;
int L[2 * dim + 2];
L[0] = 0;
L[1] = 1;
int C = 1;
int i = 0, R = 2, iMirror;
int diff;
bool expand = -1;
for (i = 2; i < N; ++i)
{
iMirror = 2 * C - i;
expand = 0;
diff = R - i;
if (diff >= 0)
{
if (L[iMirror] < diff)
L[i] = L[iMirror];
else if (L[iMirror] == diff && R == N - 1)
L[i] = L[iMirror];
else if (L[iMirror] == diff && R < N - 1)
{
expand = 1;
L[i] = L[iMirror];
}
else if (L[iMirror] > diff)
{
expand = 1;
L[i] = diff;
}
}
else
{
L[i] = 0;
expand = 1;
}
if (expand)
{
while (((i + L[i]) < N && (i - L[i]) > 0) && ( (i + L[i] + 1) % 2 == 0
|| text[(i + L[i] + 1) / 2] == text[(i - L[i] - 1) / 2]) )
L[i] ++;
}
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
}
long long ans = (N - 1) >> 1;
for (int j = 0; j < N; ++j){
if (L[j] > 1)
ans += (L[j] >> 1);
}
return ans;
}
int main()
{
string s;
cin >> s;
cout << lps(s);
return 0;
}