Pagini recente » Cod sursa (job #847129) | Cod sursa (job #451305) | Cod sursa (job #1355060) | Cod sursa (job #1156691) | Cod sursa (job #2131898)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 100007
#define mod2 100003
#define prime 73
//puterile descresc de la stanga la dreapta
//folosim 2 hashuri pentru a evita coliziunile
string a, b;
int k;
ll n, m, hasha, hasha2, hashb2, hashb, put = 1, put2 = 1;
vector <int> sol;
int main(){
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
cin >> a >> b;
n = a.length();
m = b.length();
for (int i=0; i<n; i++){
//hashuim primu string in 2 hashuri
hasha = (hasha * prime + a[i])% MOD;
hasha2 = (hasha2 * prime + a[i])% mod2;
//hashuim primele n caractere a sirului b in 2 hashuri
hashb = (hashb * prime + b[i])% MOD;
hashb2 = (hashb2 * prime + b[i])% mod2;
//calculam puterea max (m-1)
if (i){
put = (put * prime)% MOD;
put2 = (put2 * prime)% mod2;
}
}
for (int i=0; i<=m-n; i++){
if (hasha == hashb && hasha2 == hashb2) k++, sol.push_back(i);
//facem update hashului subsirului din b, x = x-char1*put + newcar
hashb = ((hashb - (b[i] * put) % MOD + MOD) * prime + b[i+n])% MOD;
hashb2 = ((hashb2 - (b[i] * put2)%mod2 + mod2) * prime + b[i+n])% mod2;
}
cout << k << "\n";
for (int i=0; i<min(k,1000); i++) cout << sol[i] << " ";
return 0;
}