Pagini recente » Cod sursa (job #18561) | Cod sursa (job #2552566) | Cod sursa (job #1204529) | Cod sursa (job #2548072) | Cod sursa (job #2976376)
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define base 69
#define MOD 100005
#define MOD1 321307
vector<int> sol;
signed 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
/*
hb -= (b[i-na] * pw) % MOD;
if(hb < 0){
hb += MOD;
}
hb *= base;
hb += b[i];
hb %= MOD;
*/
hb1 = ((hb1 - (b[i - na] * pw1) % MOD1 + MOD1) * base + b[i])% MOD1;
/*
hb1 -= (b[i-na] * pw1) % MOD1;
if(hb1 < 0){
hb += MOD1;
}
hb1 *= base;
hb1 += b[i];
hb1 %= 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 << ' ';
}
}