Pagini recente » Cod sursa (job #1701479) | Clasament 21 | Borderou de evaluare (job #1058857) | Cod sursa (job #914858) | Cod sursa (job #1075270)
#include<stdio.h>
#include<cstring>
using namespace std;
#define LMAX 2000002
char A[LMAX],B[LMAX];
int lenghtA,lenghtB,pre[LMAX],sol[LMAX],nr;
void prefix()
{
int k,i;
k=0;
pre[1]=0;
for(i=2;i<=lenghtA;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pre[k];
if(A[k+1]==A[i])
k++;
pre[i]=k;
}
}
void KMP()
{
int k=0;
for(int i=1;i<=lenghtB;i++)
{
while(k>0 && A[k+1]!=B[i])
k=pre[k];
if(A[k+1]==B[i])
k++;
if(k==lenghtA)
{
sol[++nr]=i-k;
k=pre[k];
}
}
}
int main()
{
FILE *f,*g;
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(A,LMAX,f);
fgets(B,LMAX,f);
lenghtA=strlen(A)-1;
lenghtB=strlen(B)-1;
for(int i=lenghtA;i>0;i--)
A[i]=A[i-1];
A[0]=' ';
for(int i=lenghtB;i>1;i--)
B[i]=B[i-1];
B[0]=' ';
prefix();
KMP();
/*
printf("A=%s\n", A);
printf("B=%s\n", B);
printf("%d\n", lenghtA);
printf("%d\n", lenghtB);
for(int i=1;i<=lenghtA;i++)
printf("%d ",pre[i]);
*/
fprintf(g,"%d\n",nr);
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;i++)
fprintf(g, "%d ",sol[i]);
fclose(f);
fclose(g);
return 0;
}