Pagini recente » Cod sursa (job #314082) | Cod sursa (job #1027127) | Cod sursa (job #466132) | Cod sursa (job #1585911) | Cod sursa (job #3206390)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1=1e5+7;
const int mod2=1e5+21;
const int p=73;
string A;
string B;
int h1a,h2a,p1,p2;
int a,b;
vector <int > ans;
int main()
{
f>>A;
f>>B;
a=A.size();
b=B.size();
if(a>b)
{cout<<0;
return 0;
}
p1=p2=1;
h1a=h2a=0;
for(int i=0; i<a; i++)
{
h1a=(h1a*p +A[i])%mod1;
h2a=(h2a*p +A[i])%mod2;
if(i)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
int h1=0,h2=0;
for(int i=0; i<a; i++)
{
h1=(h1*p +B[i])%mod1;
h2=(h2*p +B[i])%mod2;
}
if(h1a==h1 && h2a==h2)
ans.push_back(0);
for(int i=a; i<b; i++)
{
h1=((h1-(B[i-a]*p1)%mod1+mod1)*p+B[i])%mod1;
h2=((h2-(B[i-a]*p2)%mod2+mod2)*p+B[i])%mod2;
if(h1==h1a && h2==h2a)
ans.push_back(i-a+1);
}
int nr=0;
g<<ans.size()<<'\n';
for(auto it : ans)
{
++nr;
g<<it<<' ';
if(nr==1000)
break;
}
return 0;
}