Pagini recente » Cod sursa (job #3201292) | Cod sursa (job #3177323) | Cod sursa (job #1658315) | Cod sursa (job #1783557) | Cod sursa (job #807152)
Cod sursa(job #807152)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char PAT[2000000];
char TEX[2000000];
char S[4000000];
char T[1000];
int Z[4000000];
int l,r,n,i,p,q;
int k,kp;
int lung,rez;
int main()
{
f.getline(PAT,2000000);
lung=strlen(PAT);
f.getline(TEX,2000000);
n=strlen(PAT)+strlen(TEX)+1;
S[0]='$';
S[1]='\0';
strcat(S,PAT);
strcat(S,"$");
strcat(S,TEX);
strcat(S,"$");
// se calculeaza Z[2];
k=2;
i=1;
while (S[k]==S[i])
{
k++;
i++;
}
Z[2]=i-1;
r=Z[2];
l=1;
// se calculeaza Z[k]
for (k=3;k<=n;k++)
if (k>r)
{
p=k;
i=1;
while (S[p]==S[i])
{
p++;
i++;
}
Z[k]=i-1;
r=Z[k];
l=k;
}
else
{
kp=k-l+1;
if (Z[kp]<r-k+1)
Z[k]=Z[kp];
else
{
q=k;
i=1;
while (S[q]==S[i])
{
q++;
i++;
}
Z[k]=q-k;
r=q-1;
l=k;
}
}
rez=0;
for (i=1;i<=n;i++)
if (Z[i]==lung)
rez++;
g<<rez<<'\n';
for (i=1;i<=n;i++)
if (Z[i]==lung)
g<<i-lung-2<<" ";
f.close();
g.close();
return 0;
}