Pagini recente » Cod sursa (job #953460) | Cod sursa (job #154640) | Profil Moldo97 | Cod sursa (job #1587748) | Cod sursa (job #608963)
Cod sursa(job #608963)
#include <stdio.h>
#include <string.h>
#define NMax 2000005
int NrAp=0;
int VcAp[1000];
int h=0;
char A[NMax],B[NMax];
int pi[NMax];
int m,n;
FILE *f,*g;
void prefix(char P[])
{
int k=0,q;
for( q=1,pi[1]=0;q<=m;q++)
{
while(k>0 &&P[k] != P[q])
k=pi[k];
if(P[k] == P[q])
k=k+1;
pi[q]=k;
}
return;
}
void KMP(char P[], char T[])
{
int q;
prefix(P);
q=0;
for(int i=0;i<=n;i++)
{
while(q>0 && P[q] != T[i])
q=pi[q];
if(P[q] == T[i])
q=q+1;
if(q==m)
{
VcAp[h++] = i-m+1;
q=pi[q-1];
}
}
}
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(A, sizeof(A), f);
fgets(B, sizeof(B), f);
m=strlen(A);
n=strlen(B);
KMP(A,B);
fprintf(g,"%d \n",h);
for(int i=0;i<h;i++)
fprintf(g,"%d ",VcAp[i]);
scanf("%d");
return 0;
}