Pagini recente » Istoria paginii runda/mda3/clasament | Cod sursa (job #488844) | Cod sursa (job #1003370) | Cod sursa (job #1912529) | Cod sursa (job #1013070)
#include <fstream>
#include <string.h>
#define Nmax 1000099
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int N,P[2*Nmax],C,R;
char S[Nmax],T[2*Nmax];
inline void ReadInput()
{
f.getline(S+1,Nmax,'\n');
N=strlen(S+1);
}
inline void Preprocess()
{
//din "abba" fac "^#a#b#b#a#$"
T[0]='^';T[1]='#';
for(int i=1;i<=N;++i)T[2*i]=S[i],T[2*i+1]='#';
T[2*N+2]='$';
N*=2;
}
inline int FindLPS(char T[])
{
for(int i=1;i<=N;++i)
{
int i_mirror=2*C-i;
if(R>i)P[i]=min(R-i,P[i_mirror]);
else P[i]=0;
while(T[i+1+P[i]] == T[i-1-P[i]])++P[i];
if(i+P[i]>R)
{
C=i;
R=i+P[i];
}
}
}
inline void PrintLPS()
{
int maxLen=0,centerIndex=0;
for(int i=1;i<=N;++i)
if(P[i]>maxLen)
{
maxLen=P[i];
centerIndex=i;
}
g<<maxLen<<'\n';
//int st=(centerIndex-1-maxLen)/2; g<<st<<'\n';
//for(int i=1;i<=maxLen;++i)g<<S[st+i];
}
int main()
{
ReadInput();
Preprocess();
FindLPS(T);
PrintLPS();
f.close();g.close();
return 0;
}