Pagini recente » Cod sursa (job #103975) | Cod sursa (job #1727126) | Cod sursa (job #2517356) | Cod sursa (job #2848750) | Cod sursa (job #1518306)
#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[5] = { 1000003, 1000037, 1000121, 1000159, 1000187 };
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" );
fgets ( v1, MAXLEN, fin ); /// string to be searched
fgetc ( fin ); /// '\n'
fgets ( v2, MAXLEN, fin ); /// 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
len -= 2; len2 -= 2;
for ( MODcount = 0; MODcount < 5; 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];
num1 %= 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 - 2;
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;
}