Pagini recente » Cod sursa (job #1721208) | Cod sursa (job #346304) | Cod sursa (job #890121) | Cod sursa (job #1504699) | Cod sursa (job #760697)
Cod sursa(job #760697)
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
char A[ LMAX ], B[ LMAX ];
int len1, len2, L[ LMAX ], v [ LMAX ], nr;
void read()
{
char c;
FILE *f = fopen("strmatch.in", "r");
fscanf(f, "%c", &c);
while(c != '\n')
{
len1++;
A[ len1 ] = c;
fscanf(f, "%c", &c);
}
fscanf(f, "%c", &c);
while(c != '\n')
{
len2++;
B[ len2 ] = c;
fscanf(f, "%c", &c);
}
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++, v[nr] = i - len1, k = L[k];
}
}
void write()
{
int q;
FILE *g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", nr);
for(q = 1; q <= nr; q++)
fprintf(g, "%d ", v[q]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
read();
Prefix();
KMP();
write();
return 0;
}