Pagini recente » Borderou de evaluare (job #1532007) | Cod sursa (job #3032723) | Cod sursa (job #3269896) | Cod sursa (job #665999) | Cod sursa (job #2041993)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char P[2000002],T[2000002],S[4000004];
int Z[4000004];
int n,m,ck,beta;
int L,R,ind1,ind2;
int rez;
int main()
{
fi>>P;
fi>>T;
n=strlen(P);
strcpy(S,"*");
strcat(S,P);
strcat(S,"$");
strcat(S,T);
m=strlen(S+1);
Z[1]=0;
L=1;
R=1;
for (int k=2;k<=m;k++)
if (S[k]!=S[1])
;
else
if (k>R)
{
ind1=1;
ind2=k;
while (S[ind1]==S[ind2])
{
ind1++;
ind2++;
}
Z[k]=ind1-1;
L=k;
R=ind2-1;
}
else
{
ck=k-(L-1);
beta=R-(k-1);
if (Z[ck]<beta)
Z[k]=Z[ck];
else
{
Z[k]=beta;
ind2=R+1;
ind1=1+beta;
while (S[ind1]==S[ind2])
{
Z[k]++;
ind1++;
ind2++;
}
if (k+Z[k]-1>R)
{
L=k;
R=k+Z[k]-1;
}
}
}
/*
for (int i=1;i<=m;i++)
fo<<S[i]<<" ";
fo<<"\n";
for (int i=1;i<=m;i++)
fo<<Z[i]<<" ";
fo<<"\n";
*/
for (int i=n+2;i<=m;i++)
if (Z[i]==n)
rez++;
fo<<rez<<"\n";
int nr=0;
for (int i=n+2;i<=m;i++)
if (Z[i]==n)
{
fo<<i-n-2<<" ";
nr++;
if (nr==1000)
break;
}
fi.close();
fo.close();
return 0;
}