Pagini recente » Cod sursa (job #259599) | Cod sursa (job #2294466) | Cod sursa (job #2068666) | Cod sursa (job #848703) | Cod sursa (job #2792830)
#include <stdio.h>
#include <string.h>
#define LMAXX 2000000
#define HASHSIZE 666013
#define BAZAHASH 256
#define POZMAXX 1000
using namespace std;
FILE *fin, *fout;
char sirA[LMAXX + 1], sirB[LMAXX + 1];
int poz[POZMAXX], lungA, lungB;
int put( int a, int n ) {
int p;
p = 1;
while( n ) {
if ( n % 2 == 1 )
p = (long long)p * a % HASHSIZE;
a = (long long)a * a % HASHSIZE;
n /= 2;
}
return p;
}
int computeHash( char v[], int size ) {
int hash, i;
hash = i = 0;
while ( i < size ) {
hash = ( hash * BAZAHASH + v[i] ) % HASHSIZE;
i++;
}
return hash;
}
int add( char ch, int hash ) {
return ( hash * BAZAHASH + ch ) % HASHSIZE;
}
int erase( char ch, int hash, int pow ) {
hash -= ch * pow % HASHSIZE;
if ( hash < 0 ) {
hash += HASHSIZE;
}
return hash;
}
void afis( int n ) {
int i;
fprintf( fout, "%d\n", n );
for ( i = 0; i < n; i++ ) {
fprintf( fout, "%d ", poz[i] );
}
}
bool cmp( char v1[], char v2[] ) {
int i;
i = 0;
while ( v1[i] && v2[i] && v1[i] == v2[i] )
++i;
return v2[i] == 0;
}
void search( char v1[], int size1, char v2[], int size2 ) {
int i, hashA, hashB, pow, cnt;
hashB = computeHash( v2, size2 );
hashA = computeHash( v1, size1 );
pow = put( BAZAHASH, size2 - 1 );
cnt = 0;
i = size2;
while ( i <= size1 ) {
hashA = add( v1[i - 1], hashA );
if ( cmp( v1 + i - size2, v2 ) ) {
poz[cnt] = i - size2;
cnt++;
}
hashA = erase( v1[i - 1], hashA, pow );
i++;
}
afis( cnt );
}
int main()
{
fin = fopen( "strmatch.in", "r" );
fout = fopen( "strmatch.out", "w" );
fgets( sirB, LMAXX + 1, fin );
lungB = strlen( sirB );
if ( sirB[lungB - 1] == '\n' )
sirB[--lungB] = 0;
fgets( sirA, LMAXX + 1, fin );
lungA = strlen( sirA );
if ( sirA[lungA - 1] == '\n' )
sirA[--lungA] = 0;
fclose( fin );
search( sirA, lungA, sirB, lungB );
fclose( fout );
return 0;
}