Pagini recente » Istoria paginii runda/for_begginers/clasament | Cod sursa (job #726871) | Rating Florea Catalin (Florea_Catalin_324CC) | Cod sursa (job #3241390) | Cod sursa (job #478503)
Cod sursa(job #478503)
#include<stdio.h>
#include<string.h>
char *A, *B;
int *p, *matchPos, lengthA, lengthB, lengthMatch;
void prefix(){
int k = -1;
p[0] = -1;
for(int i=1; i<lengthA; i++) {
while(k >= 0 && A[i] != A[k+1])
k = p[k];
if(A[k+1] == A[i]) ++k;
p[i] = k;
}
}
void match(){
prefix();
int q = -1;
for(int i=0; i<lengthB; i++){
while(q+1 == lengthA || (q >= 0 && A[q+1] != B[i]))
q = p[q];
if(A[q+1] == B[i]) ++q;
if(q == lengthA - 1)
if(lengthMatch < 1000) matchPos[lengthMatch++] = i - lengthA + 1;
else ++lengthMatch;
}
}
void read(){
FILE *ifile;
A = new char[2000000];
B = new char[2000000];
p = new int[2000000];
matchPos = new int[1000];
ifile = fopen("strmatch.in", "r");
fscanf(ifile, "%s", A);
fscanf(ifile, "%s", B);
lengthA = strlen(A);
lengthB = strlen(B);
fclose(ifile);
}
void write(){
FILE *ofile;
ofile = fopen("strmatch.out", "w");
fprintf(ofile, "%i\n", lengthMatch);
if(lengthMatch > 1000) lengthMatch = 1000;
for(int i=0; i<lengthMatch; i++)
fprintf(ofile, "%i ", matchPos[i]);
fclose(ofile);
}
int main()
{
read();
match();
write();
return 0;
}