Pagini recente » Cod sursa (job #1393331) | Cod sursa (job #1674712) | Cod sursa (job #1467776) | Cod sursa (job #2884696) | Cod sursa (job #156201)
Cod sursa(job #156201)
#include<stdio.h>
#include<cstring>
#define vv 2000005
int n,m,p[vv],q,s[1024];
char a[vv],w[vv];
void citire(int &n, char a[])
{
//scanf("%d",&n);
//for (int i=0; i<n; i++)
// scanf("%d",&a[i]);
fgets(a,vv,stdin);
if (a[strlen(a)-1]=='\n')
a[strlen(a)-1]=0;
n=strlen(a);
}
void prec()
{
int k=0;
p[1]=0;
for (int i=2; i<=m; i++)
{
while (k>0 && w[k+1]!=w[i])
k=p[k];
if (w[k+1]==w[i])
++k;
p[i]=k;
}
}
void kmp()
{
for (int i=1; i<=n; i++)
{
while (q>0 && w[q+1]!=a[i])
q=p[q];
if (w[q+1]==a[i])
++q;
if (q==m)
{
++s[0];
q=p[m];
if (s[0]<=1000)
s[s[0]]=i-m;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire(m,w);
citire(n,a);
for (int i=n; i; --i)
a[i]=a[i-1];
a[0]=' ';
for (int i=m; i; --i)
w[i]=w[i-1];
w[0]=' ';
fclose(stdin);
prec();
kmp();
printf("%d\n",s[0]);
if (s[0]>1000)
s[0]=1000;
for (int i=1; i<=s[0]; i++)
printf("%d ",s[i]);
fclose(stdout);
return 0;
}