Pagini recente » Cod sursa (job #889728) | Cod sursa (job #996587) | Cod sursa (job #191791) | Cod sursa (job #1012950) | Cod sursa (job #2391102)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define MAXIM 2000010
#define d 256
#define q 100007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[MAXIM], B[MAXIM];
int hashA, hashB, power = 1, nrSol;
vector <int> G;
int main()
{
f >> A >> B;
for(unsigned int i = 0; i < strlen(A); i++)
{
hashA = (hashA * d + A[i]) % q;
hashB = (hashB * d + B[i]) % q;
if(i) power = (power * d) % q;
}
//cout << hashA << '\n';
for(unsigned int i = 0; i <= strlen(B) - strlen(A); i++)
{
// cout << hashB << '\n';
if(hashA == hashB)
{
int ok = 1;
for(unsigned int j = 0; j < strlen(A) && ok; j++)
if(A[j] != B[i + j]) ok = 0;
nrSol++;
if(nrSol < 999) G.push_back(i);
}
if(i != strlen(B) - strlen(A))
{
//cout << B[i] << ' ' << B[i + strlen(A)] << '\n';
hashB = ((hashB - B[i] * power) % q * d + B[i + strlen(A)]) % q;
if(hashB < 0) hashB = q + hashB;
}
}
g << nrSol << '\n';
for(unsigned int i = 0; i < G.size(); i++)
g << G[i] << ' ';
f.close();
g.close();
return 0;
}