Pagini recente » Cod sursa (job #3162976) | Cod sursa (job #559593) | Cod sursa (job #2125796) | Cod sursa (job #2419250) | Cod sursa (job #3214360)
#include <bits/stdc++.h>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> sol;
string s,t;
int n,p,p1,p2,ha1,hb1,ha2,hb2;
int main()
{
int i;
fin >> s >> t;
n=s.size();
p=73;
p1=p2=1;
for(i=0;i<n;i++){
ha1=(ha1*p+s[i])%MOD1;
ha2=(ha2*p+s[i])%MOD2;
if(i!=0){
p1=(p1*p)%MOD1;
p2=(p2*p)%MOD2;
}
}
for(i=0;i<n;i++){
hb1=(hb1*p+t[i])%MOD1;
hb2=(hb2*p+t[i])%MOD2;
}
if(hb1==ha1 && hb2==ha2) sol.push_back(0);
for(;i<t.size();i++){
hb1=((hb1-(t[i-n]*p1)%MOD1+MOD1)*p+t[i])%MOD1;
hb2=((hb2-(t[i-n]*p2)%MOD2+MOD2)*p+t[i])%MOD2;
if(hb1==ha1 && hb2==ha2) sol.push_back(i-n+1);
}
fout << sol.size() << "\n";
n=sol.size();
for(i=0;i<min(1000,n);i++) fout << sol[i] << " ";
return 0;
}