Pagini recente » Cod sursa (job #3286646) | Cod sursa (job #313192) | Cod sursa (job #2915577) | Cod sursa (job #2140685) | Cod sursa (job #1425334)
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
#define nmax 4000100
FILE *f,*g;
char a[nmax],b[nmax/2];
int Z[nmax];
int P;
int sol[1010],cn;
void Z_algorithm()
{
int L,R,i,j,k,n = strlen(a),ind,d;
L = R = 0;
for (i=2;i<n;i++)
{
if (i>R)
{
if (a[1] == a[i])
{
L = i;
for (j=1,k=i,R=i-1;k<n && a[j] == a[k];j++,k++) Z[i]++,R++;
}
else
Z[i] = 0;
}
else
{
ind = i-L+1;
if (Z[ind]<R-i+1)
{
Z[i] = Z[ind];
}
else
{
Z[i] = R-i+1;
d =Z[i]+1;
for(;R+1<n && a[R+1] == a[d];R++,d++) Z[i]++;
}
}
if (i>P && Z[i]>=P)
{
if (cn<1000)
sol[++cn] = i-P-1;
else
cn++;
}
}
}
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
a[0] = '~';
fscanf(f,"%s",a+1);
P = strlen(a)-1;
fscanf(f,"%s",b);
strcat(a,b);
Z_algorithm();
fprintf(g,"%d\n",cn);
if (cn<1000)
for (int i=1;i<=cn;i++)
fprintf(g,"%d ",sol[i]);
else
for (int i=1;i<=1000;i++)
fprintf(g,"%d ",sol[i]);
return 0;
}