Pagini recente » Profil pelokbence575 | Cod sursa (job #3296755)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int MOD = 1e9+7;
int baza = 1024;
int pws[2000005],hsh[2000005];
void Build_Rolly_Hashy_Hash(string S){
int n = S.size();
for (int i=n-1;i>=0;--i) hsh[i] = ((1LL*hsh[i+1]*baza)%MOD+S[i])%MOD;
return;
}
void Build_Powery_Powers(string S){
int n = S.size();
pws[0] = 1;
for (int i=1;i<=n;++i) pws[i] = (1LL*pws[i-1]*baza)%MOD;
return;
}
int Build_Hashy_Hash(string S){
int n = S.size(),h = 0;
for (int i=n-1;i>=0;--i) h = ((1LL*h*baza)%MOD+S[i])%MOD;
return h;
}
int GetSeq(int L,int R){
return ((hsh[L]-(1LL*hsh[R+1]*pws[R-L+1])%MOD)%MOD+MOD)%MOD;
}
int main()
{
string a,b;
fin >> a;
fin >> b;
Build_Rolly_Hashy_Hash(b);
Build_Powery_Powers(b);
int h = Build_Hashy_Hash(a),ans = 0;
for (int i=0;i+a.size()-1<b.size();i++){
if (GetSeq(i,i+a.size()-1)==h) ans++;
}
fout << ans << '\n';
int cnt = 0;
for (int i=0;i+a.size()-1<b.size();i++){
if (cnt<1000 and GetSeq(i,i+a.size()-1)==h){
fout << i << ' ';
cnt++;
}
}
return 0;
}