Pagini recente » Cod sursa (job #1763188) | Cod sursa (job #834454) | Cod sursa (job #1504452) | Cod sursa (job #2380328) | Cod sursa (job #1577813)
#include <cstdio>
#define nmax 2000003
#include <cstring>
using namespace std;
char N[nmax],M[nmax];
int n,m,prefix[nmax],poz[nmax],rez=0;
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
N[0]=M[0]=' ';
scanf("%s",N+1);n = strlen(N);
scanf("%s",M+1);m = strlen(M);
int k=0,i;
for(i = 2;i < n;++i){
while(k!=0 && N[k+1]!=N[i])k = prefix[k];
if(N[i]==N[k+1])k++;
prefix[i]=k;
}
for(i = 1;i < m;++i){
while(k != 0 && M[i]!=N[k+1])k = prefix[k];
if(M[i] == N[k+1])k++;
if(k == n-1){
rez++;
if(rez<=1000)poz[rez] = i-n+1;
}
}
printf("%d\n",rez);
if(rez>1000)rez = 1000;
for(i = 1;i<=rez;++i)printf("%d ",poz[i]);
printf("\n");
return 0;
}