Pagini recente » Cod sursa (job #1866867) | Cod sursa (job #2443849) | Cod sursa (job #1924085) | Cod sursa (job #1683162) | Cod sursa (job #1683902)
#include<fstream>
#include<string.h>
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
#define Nmax 2000007
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int P1=1,P2=1,LA,LB,nr=0;
bool Match[Nmax];
char A[Nmax],B[Nmax];
int main()
{
f>>A>>B;
LA=strlen(A);
LB=strlen(B);
if(LA>LB)
{
g<<"0"<<'\n';
return 0;
}
int HA1=0,HA2=0,HB1=0,HB2=0;
///calculam cele doua functii Hash pentru sirul A si pentru prima portiune de lungime LA din B
for(int i=0;i<LA;++i)
{
HA1=(HA1*P+A[i])%MOD1;
HA2=(HA2*P+A[i])%MOD2;
HB1=(HB1*P+B[i])%MOD1;
HB2=(HB2*P+B[i])%MOD2;
if(i>=1) P1=(P1*P)%MOD1,P2=(P2*P)%MOD2;
}
if(HA1==HB1&&HA2==HB2) nr++,Match[0]=1;
for(int i=LA;i<LB;i++)
{
HB1=((HB1-(B[i-LA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
HB2=((HB2-(B[i-LA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
if(HA1==HB1&&HA2==HB2) nr++,Match[i-LA+1]=1;
}
g<<nr<<'\n';
nr=0;
for(int i=0;i<LB&&nr<1000;++i)
if(Match[i]) nr++, g<<i<<" ";
g<<'\n';
return 0;
}