Pagini recente » Cod sursa (job #2716650) | Cod sursa (job #3280182) | Cod sursa (job #20428) | Cod sursa (job #1437688) | Cod sursa (job #2976316)
#include <bits/stdc++.h>
using namespace std;
#define base 26
#define MOD 918723
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 pw = 1;
for(int i = 0;i<na;i++){
ha = (ha * base + a[i]) % MOD;
if(i > 0){
/// calculam puterile
pw *= base;
pw %= MOD;
}
}
/// 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, ans = 0;
for(int i = 0;i<na;i++){
hb = (hb * base + b[i]) % MOD;
}
if(ha == hb){
sol.push_back(1); /// avem seventa matchy din prima
}
for(int i = na;i<nb;i++){
/// acum ne "rostogolim"
hb = (base * (hb - b[i - na] * pw) + b[i]) % MOD;
if(hb < 0){
hb += MOD;
}
if(hb == ha){
if(sol.size() < 1000)
sol.push_back(i-na+1);
}
}
cout << sol.size() << '\n';
for(auto x: sol){
cout << x << ' ';
}
}