Pagini recente » Cod sursa (job #1316113) | Cod sursa (job #3235880) | Cod sursa (job #1551422) | Cod sursa (job #2936297) | Cod sursa (job #820410)
Cod sursa(job #820410)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
#define mod1 666013
#define mod2 2000003
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000002],b[2000002];
int v[2000002];
int nr=0;//numarul de regasiri;
int main()
{ int coda=0,codb=0,coda1=0,codb1=0;
int i,lb,la;
int p1=1,p2=1;
in>>a;
la=strlen(a);//lungimea lui a;
in>>b;
lb=strlen(b);//lungimea lui b;
if (lb<la) out<<"0";
else
{
for (i=0;i<la;i++)
{
coda = (coda*73 +a[i]) %mod1;
coda1 = (coda1*73+a[i]) %mod2;
codb = (codb*73 +b[i]) %mod1;
codb1 = (codb1*73+b[i]) %mod2;
if (i!=0)
{
p1=(p1*73)%mod1;
p2=(p2*73)%mod2;
}
}
if ((coda==codb) && (coda1==codb1))
{
v[++nr]=0;
}
for (i=la; i<lb; i++)
{
codb = (( codb -( b[i-la]*p1 ) %mod1 +mod1 )*73 + b[i] ) % mod1 ;
codb1= ((codb1 -( b[i-la]*p2 ) %mod2 +mod2 )*73 + b[i] ) % mod2 ;
if ( (coda==codb) && (coda1==codb1) )
{
v[++nr]=i-la+1;
}
}
out<<nr<<"\n";
for (i=1;i<=nr && i<=1000;i++)
out<<v[i]<<" ";
}
return 0;
}