Pagini recente » Cod sursa (job #1605015) | Cod sursa (job #1830035) | Cod sursa (job #577486) | Cod sursa (job #1606782) | Cod sursa (job #629516)
Cod sursa(job #629516)
#include <fstream>
#define MOD1 666013
#define MOD2 100021
#define B 73
using namespace std;
int sol[1002],n,m,hA1,hA2,hB1,hB2,k,putere1,putere2;
string a,b;
void brute_force(int p)
{
int i;
bool ok=1;
// for(i=p;i<=p+n-1;i++)
// if(a[i-p]!=b[i]) {ok=0; break;}
if(ok and k<1000) sol[++k]=p; else if(ok) k++;
}
int main()
{
int i;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
fi>>a;
fi>>b;
n=a.size();
m=b.size();
hA1=hB1=hB2=hA2=0; putere1=putere2=1;
for(i=0;i<n;i++)
{
hA1=(hA1*B+a[i])%MOD1;
hA2=(hA2*B+a[i])%MOD2;
hB1=(hB1*B+b[i])%MOD1;
hB2=(hB2*B+b[i])%MOD2;
if(i!=n-1) putere1=(putere1*B)%MOD1;
if(i!=n-1) putere2=(putere2*B)%MOD2;
}
if(n>m) {fo<<"0\n"; return 0;}
if(hA1==hB1 and hA2==hB2) brute_force(0);
for(i=1;i<=m-n+1;i++)
{
hB1=((hB1-((putere1*b[i-1])%MOD1)+MOD1)*B+b[i+n-1])%MOD1;
hB2=((hB2-((putere2*b[i-1])%MOD2)+MOD2)*B+b[i+n-1])%MOD2;
if(hA1==hB1 and hA2==hB2) brute_force(i);
}
fo<<k<<"\n";
for(i=1;i<=k and i<=1000;i++) fo<<sol[i]<<" ";
return 0;
}