Pagini recente » Cod sursa (job #756234) | Cod sursa (job #1872087) | Cod sursa (job #2523848) | Cod sursa (job #227134) | Cod sursa (job #1649422)
#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 main()
{
FILE *in,*out;
in=fopen("strmatch.in","r");
out=fopen("strmatch.out","w");
int i,k=0,nr=0;
char c;
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=2;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<=nr;i++)
fprintf(out,"%d ",poz[i]);
return 0;
}