Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/iullia | Monitorul de evaluare | Cod sursa (job #773043)
Cod sursa(job #773043)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000010];
char B[2000010];
int P = 79, n;
int MOD = 31179;
int mod = 30117;
int HA, ha, HB, hb, nr, v[1010], da, p, pa, i, q, qa;
int main() {
f>>A;
f>>B;
n=strlen(B)-strlen(A)-1;
//construiesc codurile hash asociat lui A = (A[0]*p^0 + A[1]*p^1 + ...) % MOD
int da = strlen(A);
p = q = 1;
for (i=0;A[i]!=0;i++) {
HA = (HA + (p*A[da-i-1]) % MOD) % MOD;
ha = (ha + (q*A[da-i-1]) % mod) % mod;
//construiesc odata cu codurile hash ale lui A si codurile hash ale primei secvente de lungime lenA din B
HB = (HB + (p*B[da-i-1]) % MOD) % MOD;
hb = (hb + (q*B[da-i-1]) % mod) % mod;
pa = p;
qa = q;
p = (p * P) % MOD;
q = (q * P) % mod;
}
if (HA == HB && ha == hb)
v[++nr]=0;
for(i=1; i<=n; i++)
{
HB = (((HB - (B[i-1] * pa) % MOD + MOD) % MOD ) * P + B[i+da-1]) % MOD;
hb = (((hb - (B[i-1] * qa) % mod + mod) % mod ) * P + B[i+da-1]) % mod;
if (HA == HB && ha == hb) {
v[++nr]=i;
if (nr > 1000) {
nr --;
break;
}
}
}
g<<nr<<"\n";
for (i=1;i<=nr;i++) {
g<<v[i] << " ";
}
g<<"\n";
}