Pagini recente » Cod sursa (job #957708) | Cod sursa (job #526968) | Cod sursa (job #3277008) | Cod sursa (job #703467) | Cod sursa (job #1553772)
///KMP
#include <cstdio>
#define maxl 2000005
#include <cstring>
using namespace std;
char M[maxl],N[maxl];
int n,m;
int prefix[maxl],poz[maxl],rez;
void citeste();
void Prefix();
void KMP();
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citeste();
Prefix();
KMP();
return 0;
}
void citeste(){
N[0] = ' '; M[0] = ' ';
gets(N+1); n = strlen(N);
gets(M+1); m = strlen(M);
}
void Prefix(){
int q = 0,i;
for(i = 2;i < n;++i){
while(q && N[q+1] != N[i])q = prefix[q];
if(N[q+1] == N[i])q++;
prefix[i] = q;
}
}
void KMP(){
int i,k = 0;
for(i = 1;i < m;++i){
while(k && N[k+1] != M[i])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]);
}