Pagini recente » Cod sursa (job #2424703) | Cod sursa (job #753700) | Cod sursa (job #2615215) | Cod sursa (job #1385427) | Cod sursa (job #1399805)
#include <fstream>
#include <cstring>
#define nmax 2000050
#define orice 661
#define mod 666013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[nmax], B[nmax], x;
int hasha, hashb, La, Lb, nrAparitii, v[nmax], p = 1;
void Hashing(char x[nmax], int &Hash){
for(int i = 0; i < Lb; ++i){
Hash = (Hash * orice % mod + (unsigned)x[i]) % mod;
}
}
void Hash2(int a){
hasha = ((hasha - (unsigned)A[a - 1] * p % mod + mod) * orice + (unsigned)A[a + Lb - 1] + mod) % mod;
}
int main()
{int i;
f>>B>>A;
La = strlen(A);
Lb = strlen(B);
for(i = 1; i < Lb; ++ i)
p = (p * orice) % mod;
Hashing(B, hashb);
Hashing(A, hasha);
if(hasha == hashb)
v[++nrAparitii] = 0;
x = La - Lb;
for(i = 1; i <= x; ++i){
Hash2(i);
// g<<hasha<<' '<<hashb<<'\n';
if(hasha == hashb){
v[++nrAparitii] = i;
}
}
g<<nrAparitii<<'\n';
for(i = 1; i <= nrAparitii; ++i)
g<<v[i]<<' ';
g<<'\n';
return 0;
}