Pagini recente » Cod sursa (job #2634555) | Cod sursa (job #233342) | Cod sursa (job #2266772) | Cod sursa (job #2312851) | Cod sursa (job #2518039)
#include <stdio.h>
#include <ctype.h>
#define NH1 666013
#define NH2 666667
#define NR_ALPHABET 26
#define B 62
#define LIM 1000
int v[2000000], poz[1000];
int code( char c ) {
int cod = 0;
if ( c >= 'A' && c <= 'Z' ) {
cod += c - 'A';
} else if ( isdigit( c ) == 1 ) {
cod += c - '0' + NR_ALPHABET * 2;
} else {
cod += c - 'a' + NR_ALPHABET;
}
return cod;
}
int main() {
FILE *fin = fopen( "strmatch.in", "r" );
FILE *fout = fopen( "strmatch.out", "w" );
int i, ap, nA, hb1, hb2, pt1, pt2, h1, h2, st, dr;
char c;
c = fgetc( fin );
h1 = h2 = nA = 0;
pt1 = pt2 = 1;
while ( c != '\n' ) {
h1 = (h1 + code( c ) * pt1) % NH1;
h2 = (h2 + code( c ) * pt2) % NH2;
pt1 = (pt1 * B) % NH1;
pt2 = (pt2 * B) % NH2;
++nA;
c = fgetc( fin );
}
c = fgetc( fin );
hb1 = hb2 = 0;
pt1 = pt2 = 1;
i = 0;
while ( i < nA && c != '\n' ) {
hb1 = (hb1 + code( c ) * pt1) % NH1;
hb2 = (hb2 + code( c ) * pt2) % NH2;
pt1 = (pt1 * B) % NH1;
pt2 = (pt2 * B) % NH2;
v[i] = code( c );
c = fgetc( fin );
++i;
}
pt1 /= B;
pt2 /= B;
ap = st = i = 0;
dr = nA;
while ( c != '\n' ) {
if ( ap < LIM ) {
if ( h1 == hb1 && h2 == hb2 ) {
poz[ap] = st;
++ap;
}
}
hb1 = (((hb1 - v[st]) / B) + code( c ) * pt1) % NH1;
hb2 = (((hb2 - v[st]) / B) + code( c ) * pt2) % NH2;
v[dr] = code( c );
++dr;
++st;
c = fgetc( fin );
}
if ( ap < LIM ) {
if ( h1 == hb1 && h2 == hb2 ) {
poz[ap] = st;
++ap;
}
}
fprintf( fout, "%d\n", ap );
for ( i = 0; i < ap; ++i ) {
fprintf( fout, "%d ", poz[i] + 1 );
}
fclose( fin );
fclose( fout );
return 0;
}