Pagini recente » Cod sursa (job #1815720) | Cod sursa (job #1188389) | Cod sursa (job #854616) | Cod sursa (job #745419) | Cod sursa (job #2974872)
#include <bits/stdc++.h>
#define SIGMA 62
#define MOD 333173
using namespace std;
string a,b;
int hasha,hashb,ans;
vector<int> sol;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
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()
{
fin >> a >> b;
if(a.size() > b.size()){
fout << "0";
return 0;
}
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++;
sol.push_back(1);
}
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);
}
}
}
fout << ans << "\n";
for(int it: sol){
fout << it << " ";
}
return 0;
}