Pagini recente » Cod sursa (job #505076) | Cod sursa (job #1080132) | Cod sursa (job #1936403) | Cod sursa (job #2037179) | Cod sursa (job #3299080)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int mod=1e9+7;
const int nmax=2e6;
const int base=512;
int bases[nmax+5], rollinghash[nmax+5], rez[1005];
string s, t;
void buildbase ()
{
bases[0]=1;
for (int i=1; i<=nmax; i++)
bases[i]=(bases[i-1]*1LL*base)%mod;
}
int buildhash (string s)
{
int h=0;
for (int i=s.size()-1; i>=0; i--)
h=(h*1LL*base+s[i])%mod;
return h;
}
void rollhash (string s)
{
for (int i=s.size()-1; i>=0; i--)
rollinghash[i]=(rollinghash[i+1]*1LL*base+s[i])%mod;
}
int hinterval (int st, int dr)
{
return ((rollinghash[st]-rollinghash[dr+1]*1LL*bases[dr-st+1])%mod+mod)%mod;
}
int main()
{
fin >> s >> t;
buildbase();
int hash=buildhash(s);
rollhash(t);
int m=0;
for (int i=0; i+s.size()<=t.size(); i++)
{
if (hash==hinterval(i,i+s.size()-1))
{
m++;
if (m<=1000)
rez[m]=i;
}
}
fout << m << '\n';
for (int i=1; i<=min(m,1000); i++)
fout << rez[i] << ' ';
return 0;
}