Pagini recente » Borderou de evaluare (job #2690429) | Cod sursa (job #2692278)
#include <stdio.h>
#define MAXN 2000000
#define MAX_MATCH 1000
int lps[MAXN];// AFD
char src[MAXN + 2];// search
char str[MAXN + 2];
int match[MAX_MATCH];
int strLen( char *str ){
int i = 0;
while( *(str + (i++)) );
return i - 1;// scap de '\0'
}
int main(){
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int i, j, n, m, nmatch, last;
fgets(src, MAXN + 2, fin);
fgets(str, MAXN + 2, fin);
m = strLen(src);
n = strLen(str);
if( src[m - 1] == '\n' )
m--;
if( str[n - 1] == '\n' )
n--;
// calculam lps
lps[0] = last = 0;
i = 1;
while( i < m && i < 99 ){// nu avem nr. cunoscut de pasi
if( src[i] == src[last] ){
lps[i++] = ++last;
}else{
if( last > 0 )// daca inca mai putem incerca
last = lps[last - 1];// incercam prima valoare mai mica care ar putea sa mearga
else// daca am esuat
lps[i++] = 0;
}
}
// facem KMP propriu zis
i = j = 0;
nmatch = 0;
while( i < n ){// nu avamsam mereu cu o poz., putem sta pe loc cand avem missmatch
if( src[j] == str[i] ){
i++;
j++;
}else{
if( j == 0 )
i++;
else
j = lps[j - 1];// incercam urmatoarea pozitie candidata
}
if( j == m ){// daca avem match
if( nmatch < MAX_MATCH )
match[nmatch++] = i - m;
j = lps[j - 1];
}
}
fprintf(fout, "%d\n", nmatch);
nmatch = MAX_MATCH < nmatch ? MAX_MATCH : nmatch;
for( i = 0 ; i < nmatch ; i++ )
fprintf(fout, "%d ", match[i]);
fputc('\n', fout);
fclose(fin);
fclose(fout);
return 0;
}