Pagini recente » Cod sursa (job #1000805) | Cod sursa (job #2030123) | Cod sursa (job #798623) | Cod sursa (job #1886682) | Cod sursa (job #761056)
Cod sursa(job #761056)
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
char A[ LMAX ], B[ LMAX ];
int len1, len2, L[ LMAX ], v [ 1005 ], nr;
void read()
{
int i;
FILE *f = fopen("strmatch.in", "r");
fgets(A, 2000003, f);
len1 = strlen(A) - 2;
fgets(B, 2000003, f);
len2 = strlen(B) - 2;
fclose(f);
}
void Prefix()
{
int i, k;
for(i = 1; i <= len1; i++)
{
k = L[i-1];
while(k > 0 && A[k+1] != A[i])
k = L[k];
if(A[k+1] == A[i])
k++;
L[i] = k;
}
}
void KMP()
{
int i, k;
k = 0;
for(i = 0; i <= len2; i++)
{
while(k > 0 && A[k+1] != B[i])
k = L[k];
if(A[k+1] == B[i])
k++;
if(k == len1)
{
nr++;
if(nr <= 1000)
v[nr] = i - len1;
k = L[k];
}
}
}
void write()
{
int q;
FILE *g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", nr);
if(nr > 1000)
nr = 1000;
for(q = 1; q <= nr; q++)
fprintf(g, "%d ", v[q]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
read();
Prefix();
KMP();
write();
return 0;
}