Pagini recente » Cod sursa (job #1489204) | Cod sursa (job #1080081) | Cod sursa (job #2554281) | Cod sursa (job #2459322) | Cod sursa (job #733123)
Cod sursa(job #733123)
#include <stdio.h>
#include <string.h>
#define Max 2000002
using namespace std;
FILE *fin,*fout;
int main(){
char N[Max],M[Max];
int n,m,pi[Max],k;
int pos[1000],p=0;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin,"%s", N+1);
fscanf(fin,"%s", M+1);
fclose(fin);
m=strlen(M+1);
n=strlen(N+1);
pi[1]=0;
k=0;
for(int i=2;i<=n; i++){
while(k>0 && N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i])
k++;
pi[i]=k;
}
for(int q=0,i=1;i<=m;i++){
while(q>0 && N[q+1]!=M[i])
q=pi[q];
if(N[q+1]==M[i])
q++;
if(q==n){
if(p>1000) i=m+7;
else pos[p++]=i-n;
}
}
fprintf(fout,"%d\n",p);
for(int i=0;i<p;i++)
fprintf(fout,"%d ",pos[i]);
return 0;
}