Pagini recente » Cod sursa (job #2286379) | Cod sursa (job #2615870) | Cod sursa (job #1480368) | Cod sursa (job #1656422) | Cod sursa (job #2911342)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int p=666013;
const int q=100000007;
inline int prod(int u,int v)
{
u=1LL*u*v%q;
return u;
}
inline int suma(int u,int v)
{
u=(u+v)%q;
return u;
}
string a,b;
int r=1,ha,hb,nr;
vector<int>ap;
int main()
{
fin>>a>>b;
int n=a.size(),m=b.size();
for(int i=0; i<n-1; i++)
{
r=prod(r,p);
}
r=(q-r)%q;
for(int i=0; i<n; i++)
{
ha=suma(prod(ha,p),a[i]);
hb=suma(prod(hb,p),b[i]);
}
if(ha==hb)
{
nr++;
ap.push_back(1);
}
for(int dr=n; dr<m; dr++)
{
hb=suma(hb,prod(b[dr-n],r));
hb=prod(hb,p);
hb=suma(hb,b[dr]);
if(ha==hb)
{
nr++;
if(nr<=1000)
{
ap.push_back(dr-n+1);
}
}
}
fout<<nr<<'\n';
for(auto it: ap)
{
fout<<it<<' ';
}
return 0;
}