Pagini recente » Cod sursa (job #1742702) | Cod sursa (job #12773) | Cod sursa (job #2264503) | Cod sursa (job #3350413) | Cod sursa (job #3348097)
#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;
long long put[NMAX + 5];///31
long long ha;///doar pentru b fac
long long 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)
{
st--;
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;
}