Pagini recente » Cod sursa (job #1306895) | Cod sursa (job #396332) | Cod sursa (job #882010) | Cod sursa (job #2229478) | Cod sursa (job #2238030)
#include <bits/stdc++.h>
#define ll long long
#define P 59
#define MOD1 100049
#define MOD2 100057
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
ll n,m,i,hs,hp,Nr,Hp,Hs,P1=1,P2=1,a[2000005];
int main()
{
f>>p>>s;
f.close();
n=s.size();
m=p.size();
if(m>n)
{
g<<"0\n";
return 0;
}
for(i=0; i<m; i++)
{
hp=(hp*P+p[i])%MOD1;
hs=(hs*P+p[i])%MOD2;
if(i)
{
P1=(P1*P)%MOD1;
P2=(P2*P)%MOD2;
}
}
for(i=0; i<m; i++)
Hp=(Hp*P + s[i])%MOD1,
Hs=(Hs*P + s[i])%MOD2;
if(hs==Hs && Hp==hp)
Nr++,a[0]=1;
for(i=1; i<n-m+1; i++)
{
Hp=(((Hp-(s[i-1]*P1)%MOD1)+MOD1)*P+s[i+m-1])%MOD1;
Hs=(((Hs-(s[i-1]*P2)%MOD2)+MOD2)*P+s[i+m-1])%MOD2;
if(hs==Hs && Hp==hp){
Nr++,a[i]=1;
}
}
g<<Nr<<'\n';
Nr=0;
i=0;
for(i=0; i<m && Nr<1000; i++)
if(a[i])
Nr++,g<<i<<" ";
g<<'\n';
g.close();
return 0;
}