Pagini recente » Cod sursa (job #729015) | Cod sursa (job #2081299) | Cod sursa (job #2917684) | Cod sursa (job #719135) | Cod sursa (job #316594)
Cod sursa(job #316594)
#include<stdio.h>
#include<string.h>
#define NMAX 2000003
#define min(a,b) a<b?a:b
char A[NMAX],B[NMAX];
int pi[NMAX],answ[1000],n=0,a,b;
void prefixe() {
int i,k=0;
pi[1]=0;
for(i=2;i<=a;i++) {
while((k>0)&&(A[k+1]!=A[i])) k=pi[k];
if(A[k+1]==A[i]) k++;
pi[i]=k;
}
}
void KMP() {
int q=0;
for(int i=1;i<=b;i++) {
while((q>0)&&(A[q+1]!=B[i])) q=pi[q];
if(A[q+1]==B[i]) q++;
if(q==a)
if(n>=1000) n++;
else answ[n++]=i-a;
}
}
void citeste() {
freopen("strmatch.in","r",stdin);
fgets(A+1,sizeof(A),stdin);
fgets(B+1,sizeof(B),stdin);
a=strlen(A+1)-1;
b=strlen(B+1)-1;
fclose(stdin);
}
void scrie() {
freopen("strmatch.out","w",stdout);
printf("%d\n",n);
if(n>1000) n=1000;
for(int i=0;i<n;i++) printf("%d ",answ[i]);
fclose(stdout);
}
int main() {
citeste();
prefixe();
KMP();
scrie();
}