Pagini recente » Cod sursa (job #3229290) | Cod sursa (job #1448469) | Cod sursa (job #1623917) | Cod sursa (job #725610) | Cod sursa (job #3348079)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int NMAX = 2 * 1e6;
const int MOD = 1e9 + 7;
string a,b;
int put[NMAX + 5];///31
int ha;///doar pentru b fac
int hb[NMAX + 5];
void compute_hash()
{
put[0] = 1;
for(int i=1;i<=NMAX;i++)
put[i] = put[i-1] * 2936 % MOD;
for(int i=1;i<=a.size();i++)
ha = (ha + ((a[i-1] - 'A' + 1123) * put[i-1]))%MOD;
for(int i=1;i<=b.size();i++)
hb[i] = (hb[i-1] + ((b[i-1] - 'A' + 1123) * put[i-1]))%MOD;
ha = (ha * put[NMAX])%MOD;
}
///aduc startul la 31^NMAX
int queryb(int st,int dr)
{
return ((hb[dr] - hb[st-1] + MOD) * put[NMAX - st + 1])%MOD;
}
signed main()
{
fin>>a>>b;
compute_hash();
int n = a.size(), m = b.size();
vector<int> ans;
for(int i=1;i<=m-n+1;i++)
{
if(ha == queryb(i, i+n-1))
ans.push_back(i-1);
}
fout<<ans.size()<<'\n';
if(ans.size()>1000)
ans.resize(1000);
for(auto it : ans)
fout<<it<<' ';
return 0;
}