Pagini recente » Cod sursa (job #1497819) | Cod sursa (job #949784) | Cod sursa (job #2754035) | Cod sursa (job #5479) | Cod sursa (job #267128)
Cod sursa(job #267128)
#include<stdio.h>
#include<vector>
using namespace std;
#include<string.h>
#define nmax 2000001
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
char a[nmax],b[nmax];
int urm[nmax],pos[1001],A,B,nr,i,k;
void prefix()
{
int k,i;
k=-1;
urm[0]=-1;
for(i=1;i<A;i++)
{
while(k>=0 && a[k+1]!=a[i]) k=urm[k];
if(a[k+1]==a[i]) k++;
urm[i]=k;
}
}
int main()
{
fgets(a,nmax,f);
fgets(b,nmax,f);
A=strlen(a);A--;
B=strlen(b);
//fprintf(g,"%d ",B);
prefix();
k=-1;
for(i=0;i<B;i++)
{
while(k>=0 && a[k+1]!=b[i]) k=urm[k];
if(a[k+1]==b[i]) k++;
if(k==A-1)
{
nr++;
if(nr<=1000) pos[nr]=i-k;
}
}
fprintf(g,"%d\n",nr);
for(i=1;i<=min(1000,nr);i++) fprintf(g,"%d ",pos[i]);
fclose(f);
fclose(g);
return 0;
}