Pagini recente » Cod sursa (job #2212126) | Cod sursa (job #663749) | Cod sursa (job #1389715) | Cod sursa (job #972635) | Cod sursa (job #1013931)
#include <fstream>
#include <vector>
#define Nmax 1099
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int M,n,N;
vector < int > S,T;
vector < int > P[Nmax];
inline void ReadInput(vector < int > &S)
{
S.pb(-99);
for(int i=1;i<=N;++i)
{
int x;
f>>x;
S.pb(x);
}
S.pb(-88);
}
inline void Preprocess(vector < int > S, vector < int > &T)
{
//din "1234" fac "-99 -1 1 -1 2 -1 3 -1 4 - 88"
T.pb(-99);T.pb(-1);
for(int i=1;i<=N;++i)
{
T.pb(S[i]);T.pb(-1);
}
T.pb(-88);
N*=2;
}
inline int FindLPS(vector < int > T, vector < int > &P)
{
int C=0,R=0;
P.clear();
P.resize(P.size()+N+5);
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(vector < int > S,vector < int > P)
{
//for(int i=1;i<=N;++i)g<<P[i]<<' '; g<<'\n';
//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]<<' '; g<<'\n';
}
int main()
{
f>>M>>n;
for(int i=1;i<=M;++i)
{
N=n; S.clear(); T.clear();
ReadInput(S);
Preprocess(S,T);
FindLPS(T,P[i]);
PrintLPS(S,P[i]);
}
for(int i=1;i<=M;++i,g<<'\n')
for(int j=1;j<=2*n;++j)if(j%2==0)g<<P[i][j]<<' ';
f.close();g.close();
return 0;
}