Pagini recente » Cod sursa (job #2878353) | Cod sursa (job #1594793) | Cod sursa (job #2476107) | Cod sursa (job #2225335) | Cod sursa (job #1523561)
#include <stdio.h>
#include <string.h>
#define MAXLEN 2000000
char v1[MAXLEN];
char v2[MAXLEN];
char fvind[MAXLEN];
int pozsol[MAXLEN];
int pozsolfin[MAXLEN];
int modval[2] = { 1000003, 1000037 };
/// numarul initial, poz. de sters, poz. de adaugat, poz. modululului, puterea lui 123 maxima <= num
int pass ( int num, int i, int j, int x, int p123 ) { /// sterg ultima cifra si o adaug pe urmatoarea
return ( ( num - ( v2[i] * p123 ) % modval[x] + modval[x] ) * 123 + v2[j] ) % modval[x];
}
int main () {
FILE *fin, *fout;
fin = fopen ( "strmatch.in", "r" );
fout = fopen ( "strmatch.out", "w" );
fscanf( fin, "%s%s", &v1, &v2 );
int modnum, i, len = strlen ( v1 ), len2 = strlen( v2 ), p123 = 1, num1, num2; /// num1 in num2
int cnt, max = 0; /// counter, nr. maxim al contorului, pozitia lui
for ( modnum = 0; modnum < 2; modnum++ ) {
num1 = num2 = 0;
cnt = 0;
p123 = 1;
for ( i = 0; i < len; i++ ) {
num1 = ( num1 * 123 + v1[i] ) % modval[modnum];
num2 = ( num2 * 123 + v2[i] ) % modval[modnum];
}
p123 = 1;
while ( p123 * 123 <= num2 )
p123 *= 123;
i = len;
while ( i <= len2 && cnt < 1000 ) {
if ( num1 == num2 )
pozsol[cnt++] = i - len;
if ( i < len2 ) /// doar daca mai am un caracter
num2 = pass ( num2, i - len, i, modnum, p123 );
i++;
}
fvind[cnt] += ( cnt > 0 );
if ( fvind[cnt] > fvind[max] ) {
max = cnt;
for ( i = 0; i < cnt; i++ )
pozsolfin[i] = pozsol[i];
}
}
fprintf( fout, "%d\n", max );
for ( i = 0; i < max; i++ )
fprintf( fout, "%d ", pozsolfin[i] );
fclose ( fin );
fclose ( fout );
return 0;
}