Pagini recente » Cod sursa (job #406215) | Solutii preONI 2007, Runda Finala | Solutii preONI 2007, Runda Finala | Cod sursa (job #1558433) | Cod sursa (job #2047394)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int v[2000001],n;
int main()
{
string a,b;
int i,la,lb,ha1=0,ha2=0,h1=0,h2=0,p1=1,p2=1;
fin>>a>>b;
la=a.length();
lb=b.length();
for (i=0;i<la;i++)
{
ha1=(ha1*101 + a[i])%17789;
ha2=(ha2*101 + a[i])%17791;
if (i!=0)
p1=(p1*101)%17789,
p2=(p2*101)%17791;
}
for (int i=0;i<la;i++)
h1=(h1*101+b[i])%17789,
h2=(h2*101+b[i])%17791;
if (h1==ha1&&h2==ha2)
v[0]=1, n++;
for (int i=la;i <lb; i++)
{
h1=((h1-(b[i-la] * p1)% 17789 + 17789)*101 + b[i])%17789;
h2=((h2-(b[i-la] * p2)% 17791 + 17791)*101 + b[i])%17791;
if (h1==ha1&& h2==ha2)
v[i-la+1]=1, n++;
}
fout<<n<<'\n';
n=0;
for (i=0;i<lb&&n<1000;i++)
if (v[i])
n++, fout<<i<<" ";
fout<<'\n';
return 0;
}