Pagini recente » Cod sursa (job #2880114) | Cod sursa (job #504803) | Cod sursa (job #1537832) | Cod sursa (job #1093009) | Cod sursa (job #2974859)
#include <bits/stdc++.h>
#define SIGMA 62
#define MOD 333173
using namespace std;
string a,b;
int hasha,hashb,ans;
vector<int> sol;
int getpos(char ch){
if('a' <= ch && ch <= 'z'){
return (ch-'a');
}else if('A' <= ch && ch <= 'Z'){
return 26+(ch-'A');
}else{
return 52+(ch-'0');
}
}
int hashsecv(string str){
int pwr = 1;
int ans = 0;
for(int i = str.size()-1; i >= 0; i--){
ans += (getpos(str[i])*pwr)%MOD;
ans %= MOD;
pwr *= SIGMA;
pwr %= MOD;
}
return ans;
}
int main()
{
cin >> a >> b;
int pwr = 1;
for(int i = a.size()-1; i >= 0; i--){
hasha += (getpos(a[i])*pwr)%MOD;
hashb += (getpos(b[i])*pwr)%MOD;
hasha %= MOD;
hashb %= MOD;
if(i != 0){
pwr *= SIGMA;
pwr %= MOD;
}
}
if(hasha == hashb){
ans++;
}
for(int i = 1; i < b.size()-a.size()+1; i++){
hashb -= (getpos(b[i-1])*pwr)%MOD;
if(hashb < 0){
hashb += MOD;
}
hashb *= SIGMA; hashb %= MOD;
hashb += getpos(b[i+a.size()-1]); hashb %= MOD;
if(hasha == hashb){
ans++;
if(sol.size() < 1000){
sol.push_back(i);
}
}
}
cout << ans << "\n";
for(int it: sol){
cout << it << " ";
}
return 0;
}