Pagini recente » Cod sursa (job #2071288) | Cod sursa (job #3144865) | Cod sursa (job #1152911) | Cod sursa (job #2522869) | Cod sursa (job #292645)
Cod sursa(job #292645)
#include<stdio.h>
#define NMAX 2000412
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char N[NMAX],M[NMAX];
int i,j,n,m,pi[NMAX],rez[1200],p,k;
void mpre()
{ int k=0;
pi[1]=0;
for(int i=2;i<=n;++i)
{ while(k&&(N[k+1]!=N[i])) k=pi[k];
if(N[k+1]==N[i]) ++k;
pi[i]=k;
}
}
int main()
{ fgets(N,NMAX+1,f);
fgets(M,NMAX+1,f);
n=0;
m=0;
while((N[n]>='0'&&N[n]<='9')||(N[n]>='a'&&N[n]<='z')||(N[n]>='A'&&N[n]<='Z'))
++n;
while((M[m]>='0'&&M[m]<='9')||(M[m]>='a'&&M[m]<='z')||(M[m]>='A'&&M[m]<='Z')) ++m;
for(i=n;i;--i) N[i]=N[i-1];N[0]='-';
for(i=m;i;--i) M[i]=M[i-1];M[0]='-';
mpre();
k=0;
for(i=1;i<=m;++i)
{ while(k&&N[k+1]!=M[i]) k=pi[k];
if(N[k+1]==M[i]) ++k;
if(k==n) { k=pi[n];
if(p<1000) rez[++p]=i-n;
}
}
fprintf(g,"%d\n",p);
if(p>1000) p=1000;
for(i=1;i<=p;++i) fprintf(g,"%d ",rez[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}