Pagini recente » Cod sursa (job #1743234) | Cod sursa (job #2797273) | Cod sursa (job #2680240) | Cod sursa (job #3130756) | Cod sursa (job #2582752)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string x;
int lps[1000010];
int solveUsingManacher()
{
int sze = x.size();
int c = 0, r = 0;
for(int i = 0; i < sze; i++)
{
//cout << i;
int mirror = 2*c - i;
if(i < r)
lps[i] = min(lps[mirror], r - i);
int a = i + lps[i] + 1;
int b = i - lps[i] - 1;
while(a < sze && b >= 0 && x[a] == x[b])
{
lps[i]++;
a++;
b--;
}
if(i + lps[i] > r)
{
r = i + lps[i];
c = i;
}
}
/*for(int i = 0; i < sze; i++)
cout << x[i] << ' ';
cout << '\n';
for(int i = 0; i < sze; i++)
cout << lps[i] << ' ';*/
int cont = 0;
for(int i = 0; i < sze; i++)
{
if(x[i] == '#')
cont += lps[i]/2;
else
cont += (lps[i] - 1)/2 + 1;
}
return cont;
}
int main()
{
in >> x;
int sze = x.size() * 2 + 1;
for(int i = 0; i < sze; i += 2)
x.insert(i, "#");
out << solveUsingManacher() << '\n';
return 0;
}