Pagini recente » Cod sursa (job #1753714) | Cod sursa (job #1712043) | Cod sursa (job #1145784) | Cod sursa (job #3217643) | Cod sursa (job #702022)
Cod sursa(job #702022)
#include <fstream>
#include <cstring>
#define MOD1 666013
#define MOD2 999073
#define B 73
using namespace std;
int s,ha1,ha2,hb1,hb2,put1,put2,i,n,m,sol[1001];
string a,b;
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
getline(fi,a);
getline(fi,b);
m=a.size(); n=b.size();
put1=put2=1;
for(i=0;i<m;i++)
{
ha1=(B*ha1+a[i])%MOD1;
ha2=(B*ha2+a[i])%MOD2;
hb1=(B*hb1+b[i])%MOD1;
hb2=(B*hb2+b[i])%MOD2;
if(i) { put1=(put1*B)%MOD1; put2=(put2*B)%MOD2; }
}
if(ha1==hb1 and ha2==hb2) sol[++s]=0;
for(i=1;i<n-m+1;i++)
{
hb1=((hb1-(put1*b[i-1])%MOD1+MOD1)*B+b[i+m-1])%MOD1;
hb2=((hb2-(put2*b[i-1])%MOD2+MOD2)*B+b[i+m-1])%MOD2;
if(ha1==hb1 and ha2==hb2 and i<1000) sol[++s]=i; else if(ha1==hb1 and ha2==hb2) s++;
}
fo<<s<<"\n";
for(i=1;i<=s;i++) fo<<sol[i]<<" ";
fo<<"\n";
}