Pagini recente » Cod sursa (job #2799311) | Cod sursa (job #3164563) | Cod sursa (job #152755) | Cod sursa (job #1189022) | Cod sursa (job #3214359)
#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;
}
}
if (n > t.size())
{
printf("0\n");
return 0;
}
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(1);
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;
}