Pagini recente » Cod sursa (job #3001732) | Cod sursa (job #1222722) | Cod sursa (job #3279461) | Cod sursa (job #2345609) | Cod sursa (job #760703)
Cod sursa(job #760703)
#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) - 1;
for(i = len1; i >= 1; i--)
A[i] = A[i-1];
fgets(B, 2000003, f);
len2 = strlen(B) - 1;
for(i = len2; i >= 1; i--)
B[i] = B[i-1];
fclose(f);
}
void Prefix()
{
int i, k;
for(i = 2; 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 = 1; 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;
}