Pagini recente » Cod sursa (job #902697) | Cod sursa (job #310257) | Cod sursa (job #2306877) | Cod sursa (job #1108400) | Cod sursa (job #631600)
Cod sursa(job #631600)
#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[2000001],phi[2000001];
char a[2000001],b[2000001];
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(i-k<=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);
for(i1=1;i1<=nr;i1++)
printf("%d ",d[i1]);
return 0;
}