Pagini recente » Cod sursa (job #1130416) | Cod sursa (job #179103) | Cod sursa (job #2725861) | Cod sursa (job #2590752) | Cod sursa (job #3036437)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD=1e9+9;
long long hasher1(string s){
long long hs = 5381;
for(int i=0; i<s.length(); i++){
hs = (hs<<5)+hs+s[i];
hs%=MOD;
}
return hs;
}
long long hasher2(string s){
long long hs = 5381;
for(int i=0; i<s.length(); i++){
hs = (hs<<5)+5*hs+s[i];
hs%=MOD;
}
return hs;
}
int main(){
string s, t;
fin >> s >> t;
long long termH1 = hasher1(s), termH2=hasher2(s);
int ans=0;
queue<int> pos;
for(int i=0; i<t.length()-s.length(); i++){
if(termH1==hasher1(t.substr(i, s.length())) && termH2==hasher2(t.substr(i, s.length()))){
ans++;
pos.push(i);
}
}
fout << ans << '\n';
while(!pos.empty()){
fout << pos.front() << ' '; pos.pop();
}
}