Pagini recente » Cod sursa (job #1725579) | Cod sursa (job #1734959) | Cod sursa (job #1114228) | Cod sursa (job #36662) | Cod sursa (job #1198653)
#include<string.h>
#include<cstdio>
using namespace std;
char a[2000002];
char b[2000002];
int pref[2000001];
int rasp[2000001];
int k;
int main(){
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int n=1,m=1,i,pot;
scanf ("%s\n",&a);
scanf ("%s",&b);
n=strlen(a);
m=strlen(b);
for(i=n;i>0;i--) a[i]=a[i-1];
for(i=m;i>0;i--) b[i]=b[i-1];
//pref[i]= lungimea celui mai lung prefix al lui a, de lungime <i, care incepe in b[1], b[2] ... b[i]
pref[1]=0;
for(i=2;i<=n;i++){
k=pref[i-1];
while(k>0 &&a[k+1]!=a[i])
k=pref[k];
if (a[k+1]==a[i]) k++;
pref[i]=k;
//printf ("%d\n",pref[i]);
}
k=0;
pot=0;
for(i=1;i<=m;i++){
//printf ("%d\n",pot);
while(pot>0 &&a[pot+1]!=b[i])
pot=pref[pot];
//printf ("%d\n",pot);
if (a[pot+1]==b[i])
pot++;
//printf ("%d\n",pot);
if (pot==n){
k++;
rasp[k]=i-n;
}
//printf ("%d\n",pot);
}
printf ("%d\n",k);
if (k>1000) k=1000;
for(i=1;i<=k;i++)
printf ("%d ",rasp[i]);
return 0;
}