Pagini recente » Cod sursa (job #934974) | Cod sursa (job #2060681) | Cod sursa (job #767300) | Cod sursa (job #2862373) | Cod sursa (job #629487)
Cod sursa(job #629487)
#include <fstream>
#define MOD 666013
#define B 73
using namespace std;
int sol[1002],n,m,hA,hB,k,putere;
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) sol[++k]=p;
}
int main()
{
int i;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
fi>>a;
fi>>b;
n=a.size();
m=b.size();
hA=0; hB=0; putere=1;
for(i=0;i<n;i++)
{
hA=(hA*B+a[i])%MOD;
hB=(hB*B+b[i])%MOD;
if(i!=n-1) putere=(putere*B)%MOD;
}
if(n>m) {fo<<"0\n"; return 0;}
if(hA==hB) brute_force(0);
for(i=1;i<=m-n+1;i++)
{
hB=((hB-((putere*b[i-1])%MOD)+MOD)*B+b[i+n-1])%MOD;
if(hA==hB) brute_force(i);
if(k>=1000) break;
}
fo<<k<<"\n";
for(i=1;i<=k and i<=1000;i++) fo<<sol[i]<<" ";
return 0;
}