Pagini recente » Cod sursa (job #299851) | Cod sursa (job #1711476) | Cod sursa (job #1957838) | Cod sursa (job #818693) | Cod sursa (job #2586967)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string x, aux;
int lps[2000010];
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 >> aux;
int sze = aux.size();
x = "#";
for(int i = 0; i < sze; i++)
{
x += aux[i];
x += "#";
}
//cout << x;
out << solveUsingManacher() << '\n';
return 0;
}