Pagini recente » Cod sursa (job #1574138) | Cod sursa (job #2894976) | Cod sursa (job #1291491) | Cod sursa (job #1572384) | Cod sursa (job #2553485)
#include <bits/stdc++.h>
#define b1 27
#define b2 29
#define mod1 100007
#define mod2 666013
#define NM 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,nr1,nr2,h1,h2,p1,p2,nrap;
bool fr[NM];
string s,t;
void Read();
void RabinKarp();
int main()
{ Read();
RabinKarp();
return 0;
}
void Read()
{ f>>s>>t;
n=s.size();
m=t.size();
p1=p2=1;
for(int i=0; i<n; i++)
{ nr1=(nr1*b1+s[i])%mod1;
nr2=(nr2*b2+s[i])%mod2;
if(i)
{ p1=(p1*b1)%mod1;
p2=(p2*b2)%mod2;
}
}
}
void RabinKarp()
{ if(n>m)
{ g<<0;
return;
}
for(int i=0; i<n; i++)
{ h1=(h1*b1+t[i])%mod1;
h2=(h2*b2+t[i])%mod2;
}
if(nr1==h1 && nr2==h2)
nrap+=(fr[0]=1);
for(int i=n; i<m; i++)
{ h1=((h1-(t[i-n]*p1)%mod1+mod1)*b1+t[i])%mod1;
h2=((h2-(t[i-n]*p2)%mod2+mod2)*b2+t[i])%mod2;
if(h1==nr1 && h2==nr2)
nrap+=(fr[i-n+1]=1);
}
g<<nrap<<'\n';
int nrSol=0;
for(int i=0; i<NM && nrSol<1000; i++)
if(fr[i])
{ nrSol++;
g<<i<<' ';
}
}