Pagini recente » Cod sursa (job #2500593) | Cod sursa (job #2062161) | Cod sursa (job #1561280) | Cod sursa (job #2260310) | Cod sursa (job #2974880)
#include <bits/stdc++.h>
#define int long long
#define SIGMA 73
#define MOD 100007
#define MOD2 100021
using namespace std;
string a,b;
int hasha1,hasha2,hashb1,hashb2,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');
}
}
signed main()
{
fin >> a >> b;
if(a.size() > b.size()){
fout << "0";
return 0;
}
int pwr1 = 1, pwr2 = 1;
for(int i = a.size()-1; i >= 0; i--){
hasha1 += (getpos(a[i])*pwr1)%MOD;
hasha2 += (getpos(a[i])*pwr2)%MOD2;
hashb1 += (getpos(b[i])*pwr1)%MOD;
hashb2 += (getpos(b[i])*pwr2)%MOD2;
hasha1 %= MOD; hasha2 %= MOD2;
hashb1 %= MOD; hashb2 %= MOD2;
if(i != 0){
pwr1 *= SIGMA; pwr2 *= SIGMA;
pwr1 %= MOD; pwr2 %= MOD2;
}
}
if(hasha1 == hashb1 && hasha2 == hashb2){
ans++;
sol.push_back(1);
}
for(int i = 1; i < b.size()-a.size()+1; i++){
hashb1 -= (getpos(b[i-1])*pwr1)%MOD;
hashb2 -= (getpos(b[i-1])*pwr2)%MOD2;
if(hashb1 < 0){
hashb1 += MOD;
}
if(hashb2 < 0){
hashb2 += MOD2;
}
hashb1 *= SIGMA; hashb1 %= MOD;
hashb2 *= SIGMA; hashb2 %= MOD2;
hashb1 += getpos(b[i+a.size()-1]); hashb1 %= MOD;
hashb2 += getpos(b[i+a.size()-1]); hashb2 %= MOD2;
if(hasha1 == hashb1 && hasha2 == hashb2){
ans++;
if(sol.size() < 1000){
sol.push_back(i);
}
}
}
fout << ans << "\n";
for(int it: sol){
fout << it << " ";
}
return 0;
}