Pagini recente » Cod sursa (job #1138137) | Cod sursa (job #1471364) | Cod sursa (job #663387) | Cod sursa (job #124025) | Cod sursa (job #1755649)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;
int n,m,pi[NMAX],pos[1024];
char a[NMAX],b[NMAX];
int minim(int x,int y){
return (x<y)?x:y;
}
void make_prefix(){
int q=0;
for(int i=2;i<=m;++i){
pi[1]=0;
while(q&&a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
n=strlen(b),m=strlen(a);--m;--n;
for(int i=m;i;--i)a[i]=a[i-1]; a[0]=' ';
for(int i=n;i;--i)b[i]=b[i-1]; b[0]=' ';
make_prefix();
int q=0,nr=0;
for(int i=1;i<=n;++i){
while(q&&a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==m){
q=pi[m];++nr;
if(nr<=1000)
pos[nr]=i-m;
}
}printf("%d\n", nr);
for(int i=1;i<=minim(nr,1000);++i)
printf("%d ",pos[i]);
return 0;
}