Pagini recente » Cod sursa (job #144498) | Cod sursa (job #869260) | Cod sursa (job #1556539) | Cod sursa (job #1884392) | Cod sursa (job #3333365)
#include <bits/stdc++.h>
#define mod 1000000007
#define baza 131
#define int long long
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int h,H[2000001];
bool ok[2000001];
signed main()
{
string a,b;
fin>>a>>b;
for (int i=0;i<a.size();i++)
{
h=(h*baza+a[i])%mod;
H[0]=(H[0]*baza+b[i])%mod;
}
int p=1;
for (int i=1;i<a.size();i++)
{
p=(p*baza)%mod;
}
for (int i=1;i<=b.size()-a.size();i++)
{
H[i]=((H[i-1]-(b[i-1])*p)*baza+b[i+a.size()-1])%mod;
}
int nr=0;
for (int i=0;i<=b.size()-a.size();i++)
{
if (H[i]==h)
{
if (a==b.substr(i,a.size()))
{
ok[i]=1;
nr++;
}
}
}
fout<<nr<<'\n';
int x=0;
for (int i=0;i<=b.size()-a.size() && x<=1000;i++)
{
if (ok[i]==1)
fout<<i<<" ";
x++;
}
return 0;
}