Pagini recente » Cod sursa (job #871082) | Cod sursa (job #3311344) | Cod sursa (job #807170) | Monitorul de evaluare | Cod sursa (job #3348087)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
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] = 1LL * put[i-1] * 307 % MOD;
for(int i=0;i<a.size();i++)
ha = (ha + (1LL * (a[i] - 'A' + 302) * put[i]))%MOD;
for(int i=0;i<b.size();i++)
hb[i] = ((i>0 ? hb[i-1] : 0) + (1LL * (b[i] - 'A' + 302) * put[i]))%MOD;
ha = (1LL * ha * put[NMAX])%MOD;
}
///aduc startul la 31^NMAX
int queryb(int st,int dr)
{
return 1LL * (1LL * (hb[dr] - hb[st-1] + MOD) % MOD * 1LL * put[NMAX - st]) % MOD;
}
signed main()
{
fin>>a>>b;
compute_hash();
int n = a.size(), m = b.size();
vector<int> ans;
int N = 0;
for(int i=1;i<=m-n+1;i++)
{
if(ha == queryb(i, i+n-1))
{
N++;
if(N<=1000)
ans.push_back(i-1);
}
}
fout<<N<<'\n';
for(auto it : ans)
fout<<it<<' ';
return 0;
}