Pagini recente » Cod sursa (job #2451400) | Cod sursa (job #699318) | Cod sursa (job #2462020) | Cod sursa (job #267297) | Cod sursa (job #609371)
Cod sursa(job #609371)
#include <fstream>
#include <math.h>
using namespace std;
#define base_prime 73
#define big_prime 1987
//data section
char sirA[2000001], sirB[2000001];
int n, m;
int aparitii[1002], nAparitii;
long long hashB = 0, hashA = 0;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(sirB, 2000001);
fin.getline(sirA, 2000001);
n = strlen(sirA);
m = strlen(sirB);
//get hash B
for( int i = 0; i < m; i++ )
{
hashB = int (hashB + sirB[i] * pow( double( base_prime ), double( m - i - 1 ) ) ) % big_prime;
}
//get hash A prev
for( int i = 0; i < m; i++ )
{
hashA = int (hashA + sirA[i] * pow( double( base_prime ), double( m - i - 1 ) ) ) % big_prime;
}
if( hashA == hashB )
{
nAparitii = 1;
aparitii[1] = 0;
}
for( int i = 1; i <= n - m; i++ )
{
hashA = hashA + big_prime * pow( base_prime, double( m - 1 ) );
hashA = hashA - sirA[i-1] * pow( base_prime, double( m - 1 ) );
hashA = hashA * base_prime;
hashA = hashA + sirA[i + m - 1];
hashA = hashA % big_prime;
if( hashA == hashB && nAparitii < 1000 )
{
nAparitii++;
aparitii[nAparitii] = i;
}
}
fout << nAparitii << "\n";
for( int i = 1; i <= nAparitii; i++)
{
fout << aparitii[i] << " ";
}
fout << "\n";
return 0;
}