Pagini recente » Cod sursa (job #242892) | Cod sursa (job #2681918) | Cod sursa (job #2273345) | Cod sursa (job #276590) | Cod sursa (job #1172306)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
char ss[2000010],s[1000001];
int p[2000010],n,maxi;
long long total;
// Manacher - retinem pe parcurs palindromul care se intinde cel mai mult inspre dreapta. La punctul curent, stim ca subsecventa inclusa in palindromul maxim este cel putin la fel de mare ca palindromul maximal din partea opusa a palindromului maxim care este inclusa in palindromul maxim
int main()
{
fin>>(ss+1);
int t = strlen (ss+1);
s[n=1] = '0';
for (int i=1; i<=t; ++i)
{
s[++n] = ss[i];
s[++n] = '0';
}
//Reducem problema doar la siruri impare, introducand 0 intre fiecare nuamr
for (int i=1; i<=n; ++i)
{
int current;
if (i != 1)
current = min (p[2*maxi-i],2*maxi-i - (maxi-p[maxi]));
else current = 1;
for (; i+current<=n && i-current >=1; ++current)
{
if (s[i+current] != s[i-current])
break;
}
total += current/2;
p[i] = current;
if (p[i] + i - 1 > p[maxi] + maxi -1)
maxi = i;
}
fout<<total;
}