Pagini recente » Cod sursa (job #2894497) | Cod sursa (job #861149) | Cod sursa (job #351866) | Cod sursa (job #2240260) | Cod sursa (job #930289)
Cod sursa(job #930289)
#include <stdio.h>
#include <string.h>
using namespace std;
#define NMAX 2000005
char A[NMAX],B[NMAX];
int lena,lenb,next[NMAX],C[NMAX],c=0;
void cit()
{
fgets(A,NMAX,stdin);
fgets(B,NMAX,stdin);
lena=strlen(A)-1;
lenb=strlen(B)-1;
}
void urmator(char *P)
{
int k=-1,x;
next[0]=0;
for (x=1;x<lena;x++)
{
while (k>0 && P[k+1]!=P[x]) k=next[k];
if (P[k+1]==P[x]) k++;
next[x]=k;
}
}
void rez()
{
int i,x=-1,nr=0;
urmator(A);
for (i=0;i<lenb;i++)
{
while (x>0 && A[x+1]!=B[i]) x=next[x];
if (A[x+1]==B[i]) x++;
if (x==lena-1)
{
nr++;
C[++c]=i-lena+1;
x=next[x];
}
}
if (c>999)
c=999;
printf("%d\n",nr);
for (i=1;i<=c;i++)
printf("%d ",C[i]);
printf("\n");
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
cit();
rez();
fclose(stdin);
fclose(stdout);
return 0;
}