Pagini recente » Cod sursa (job #2323727) | Cod sursa (job #2654302) | Cod sursa (job #2628403) | Cod sursa (job #462071) | Cod sursa (job #2976348)
#include <bits/stdc++.h>
using namespace std;
#define base 97
#define MOD 918723
#define MOD1 918423
vector<int> sol;
int main(void){
ofstream cout("strmatch.out");
ifstream cin("strmatch.in");
string a,b;
cin >> a >> b;
int na = a.size();
int nb = b.size();
if(na > nb){
cout << 0;
return 0;
}
/// prima data vom calcula hashul pentru a (pattern-ul)
int ha = 0; /// hashul lui a
int ha1 = 0;
int pw = 1, pw1 = 1;
for(int i = 0;i<na;i++){
ha = (ha * base + a[i]) % MOD;
ha1 = (ha1 * base + a[i]) % MOD1;
if(i > 0){
/// calculam puterile
pw *= base;
pw %= MOD;
pw1 *= base;
pw1 %= MOD1;
}
}
/// dupa ce am obtinut hash-ul pentru pattern trebuie obtinut si pentru prima secventa de lungimen na apoi ne "rostogolim" prin celelalte secv
int hb = 0, hb1 = 0, ans = 0;
for(int i = 0;i<na;i++){
hb = (hb * base + b[i]) % MOD;
hb1 = (hb1 * base + b[i]) % MOD1;
}
if(ha == hb && ha1 == hb1){
sol.push_back(0); /// avem seventa matchy din prima
}
for(int i = na;i<nb;i++){
/// acum ne "rostogolim"
hb = ((hb - ((b[i - na] * pw)) % MOD + MOD) * base + b[i])% MOD; /// poate fi negativ
hb1 = ((hb1 - ((b[i - na] * pw1)) % MOD1 + MOD1) * base + b[i])% MOD1;
if(hb == ha && ha1 == hb1){
if(sol.size() < 1000)
sol.push_back(i-na+1);
}
}
cout << sol.size() << '\n';
for(auto x: sol){
cout << x << ' ';
}
}