Pagini recente » Cod sursa (job #1475842) | Cod sursa (job #367517) | Cod sursa (job #2033523) | Cod sursa (job #1111907) | Cod sursa (job #1518317)
#include <stdio.h>
#include <string.h>
#define MAXLEN 2000000
char v1[MAXLEN];
char v2[MAXLEN];
char fvind[MAXLEN]; /// indicii folositi
int pozsol[MAXLEN];
int pozsolfin[MAXLEN];
int modval[2] = { 1000003, 1000037 };
char getChar ( char a ) {
if ( a >= 'A' && a <= 'Z' )
return a - 'A' + 1;
else if ( a >= 'a' && a <= 'z' )
return a - 'a' + 27;
else /// a >= '0' && a <= '9'
return a - '0' + 53;
}
int pass ( int num, int nxtchr, int x ) { /// sterg ultima cifra si o adaug pe urmatoarea
int p63 = 1;
while ( p63 * 63 <= num )
p63 *= 63;
num %= p63; /// elimin prima cifra -- num = num - ( num / p63 ) * p63;
return ( num * 63 + getChar( nxtchr ) ) % modval[x];
}
int main () {
FILE *fin, *fout;
fin = fopen ( "strmatch.in", "r" );
fout = fopen ( "strmatch.out", "w" );
fscanf( fin, "%s%s", v1, v2 ); /// string to be searched, string to search inside
int MODcount, i, len = strlen ( v1 ), len2 = strlen( v2 ), p63 = 1, num1, num2; /// num to be searched;
int cnt, max = 0; /// counter, nr. maxim al contorului, pozitia lui
printf("len %d len2 %d\n", len, len2 );
for ( MODcount = 0; MODcount < 2; MODcount++ ) {
num1 = num2 = 0;
cnt = 0;
p63 = 1;
for ( i = len - 1; i >= 0; i--, p63 *= 63, num1 %= modval[MODcount] )
num1 += ( p63 * getChar( v1[i] ) ) % modval[MODcount];
p63 = 1;
for ( i = len - 1; i >= 0; i--, p63 *= 63, num2 %= modval[MODcount] )
num2 += ( p63 * getChar( v2[i] ) ) % modval[MODcount];
for ( i = len; i <= len2; i++ ) {
if ( num1 == num2 )
pozsol[cnt++] = i - len;
num2 = pass ( num2, v2[i], MODcount );
}
fvind[cnt]++;
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;
}