Pagini recente » Cod sursa (job #893834) | Cod sursa (job #1697078) | Cod sursa (job #1388850) | Cod sursa (job #2665343) | Cod sursa (job #580863)
Cod sursa(job #580863)
#include <stdio.h>
#include <string.h>
#define maxn 2000022
char A[maxn], B[maxn];
int pi[maxn], pos[1033];
int matches;
void match()
{
int lena = strlen(A), lenb = strlen(B);
int i = 0, j = 0;
for (i = 0; i <= lenb - lena; i++)
{
j = 0;
while (j < lena && A[j] == B[i+j])
j++;
if (j == lena)
if (matches > 1000)
matches++;
else
pos[matches++] = i;
}
}
void prefix()
{
int i = 0, k = 0, lena = strlen(A);
pi[1] = 0;
for (i = 2; i <= lena; i++)
{
while (k > 0 && A[k] != A[i - 1])
k = pi[k];
if (A[k] == A[i - 1])
k++;
pi[i] = k;
}
//for (i = 1; i <= lena; i++)
// printf("%d ", pi[i]);
}
void match_kmp()
{
int lena = strlen(A), lenb = strlen(B);
int i = 0, q = 0;
for (i = 0; i < lenb; i++)
{
while (q > 0 && A[q] != B[i])
q = pi[q];
if (A[q] == B[i])
q = q + 1;
//printf("%d %d\n", i, q);
if (q == lena)
if (matches > 1000)
matches++;
else
pos[matches++] = i - lena + 1;
}
}
int main()
{
FILE *fin = fopen("strmatch.in", "rt");
FILE *fout = fopen("strmatch.out", "wt");
int i = 0;
fscanf(fin, "%s\n%s", A, B);
prefix();
match_kmp();
fprintf(fout, "%d\n", matches);
for (i = 0; i < ((matches > 1000) ? 1000 : matches); i++)
fprintf(fout, "%d ", pos[i]);
fclose(fin), fclose(fout);
return 0;
}