Pagini recente » Cod sursa (job #1126072) | Cod sursa (job #954048) | Cod sursa (job #835984) | Cod sursa (job #393169) | Cod sursa (job #1649453)
#include <cstdio>
using namespace std;
const int N=2000005;
char a[N],b[N];
int pi[N],poz[N];
int nra,nrb;
void prelucrare()
{
int k=0,i;
pi[1]=0;
for(i=2;i<=nra;i++)
{
while(k!=0 && a[k+1]!=a[i])
k=pi[k];
if(a[i]==a[k+1])
k++;
pi[i]=k;
}
}
int min(int a,int b)
{
if(a<=b)
return a;
else
return b;
}
int main()
{
FILE *in,*out;
in=fopen("strmatch.in","r");
out=fopen("strmatch.out","w");
int i,k=0,nr=0;
fgets(a,N-1,in);
fgets(b,N-1,in);
for(i=0;a[i]!='\n';i++)
nra++;
for(i=0;b[i]!='\n';i++)
nrb++;
for(i=nra;i>=1;i--)
a[i]=a[i-1];
for(i=nrb;i>=1;i--)
b[i]=b[i-1];
prelucrare();
for(i=1;i<=nrb;i++)
{
while(k!=0 && b[i]!=a[k+1])
k=pi[k];
if(b[i]==a[k+1])
k++;
if(k==nra)
{
nr++;
k=pi[nra];
if(nr<=1000)
poz[nr]=i-nra;
}
}
fprintf(out,"%d\n",nr);
if(nr!=0)
for(i=1;i<=min(nr,1000);i++)
fprintf(out,"%d ",poz[i]);
return 0;
}