Pagini recente » Cod sursa (job #1817470) | Cod sursa (job #1633599) | Cod sursa (job #1788305) | Cod sursa (job #774059) | Cod sursa (job #772867)
Cod sursa(job #772867)
#define abs(x) ((x>0)?x:x*-1)
#define max(a,b) ((a>b)?a:b)
#include<stdio.h>
#include<cstring>
using namespace std;
int i1,n,m,nr,d[1006],phi[2000004];
char a[2000004],b[2000004];
int prefix()
{
int k,i;
k=0;
phi[1]=0;
for(i=2;i<=m;i++)
{
while(k!=0&&b[i]!=b[k+1]) k=phi[k];
if(b[i]==b[k+1]) k++;
phi[i]=k;
}
}
int kmpp()
{
int k,i;
k=0;
for(i=1;i<=n;i++)
{
while(k!=0&&a[i]!=b[k+1]) k=phi[k];
if(a[i]==b[k+1]) k++;
if(k==m)
{
nr++;
if(nr<=1000) d[nr]=i-k;
k=phi[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b+1);
gets(a+1);
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmpp();
printf("%d\n",nr);
if(nr>1000) nr=1000;
for(i1=1;i1<=nr;i1++)
printf("%d ",d[i1]);
return 0;
}