Pagini recente » Cod sursa (job #1478717) | Cod sursa (job #762338) | Cod sursa (job #2728691) | Cod sursa (job #3265026) | Cod sursa (job #165016)
Cod sursa(job #165016)
#include<stdio.h>
using namespace std;
char a[2000002], b[2000002];
int m, n, lim, r[1024], pi[2000002];
void prefix(){
int i, k;
pi[1]=0;
k=0;
for(i=2;i<=m;i++){
while(k && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
k++;
pi[k]=k;
}
}
void match(){
int i, k;
k=0;
for(i=1;i<=n;i++){
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==m)
{
lim++;
k=pi[k];
if(lim<1001) r[lim]=i-m+1;
}
}
}
int main(){
freopen("strmatch.in","r", stdin);
fgets(A+1, sizeof(A), stdin);
fgets(B+1, sizeof(B), stdin);
fclose(stdin);
n=1;while(b[n]) n++; n--;
m=1; while(a[m]) m++; m--;
prefix();
match();
freopen("strmatch.out","w",stdout);
printf("%d\n",lim);
int i, min;
min=(1000<lim)?1001:(lim+1);
for(i=1;i<min;i++)
printf("%d ",r[i]);
fclose(stdout);
return 0;
}