Pagini recente » Cod sursa (job #2654775) | Cod sursa (job #2043500) | Cod sursa (job #2775874) | Cod sursa (job #13228) | Cod sursa (job #489293)
Cod sursa(job #489293)
// infoarena: problema/strmatch //
#include <string.h>
#include <stdio.h>
#define MAXN 2000100
FILE *in, *out;
char a[MAXN],b[MAXN];
int i,j,n,m,l[MAXN],k,q,r[MAXN];
int main()
{
in = fopen("strmatch.in", "r");
out = fopen("strmatch.out", "w");
a[0] = b[0] = ' ';
fscanf(in, "%s", a+1);
fscanf(in, "%s", b+1);
n = strlen(a);
m = strlen(b);
if(n>m)
{
fprintf(out, "0");
return 0;
}
l[1] = 0;
for(i=2; i<=n; ++i)
{
while(k>0 && a[k+1] != a[i])
k = l[k];
if(a[k+1] == a[i])
++ k;
l[i] = k;
}
k=0;
for(i=1; i<=m-n+k+1; ++i)
{
while(a[k+1] != b[i] && k>0)
k=l[k];
if(a[k+1] == b[i])
++ k;
if(k+1 == n)/
r[++q] = i-n+1;
}
fprintf(out, "%d\n", q);
if(q>1000)
q=1000;
for(i=1; i<=q; ++i)
fprintf(out, "%d ", r[i]);
return 0;
}