Pagini recente » Cod sursa (job #363522) | Cod sursa (job #2099457)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const long long MOD1=1e9+7,BAZA=75;
vector <int> v;
string a,b;
long long val1,p1,n,m,rhash1;
int main()
{
fi>>a;
fi>>b;
n=a.size();
m=b.size();
p1=1;
for(int i=0;i<n;i++)
{
val1=(val1*BAZA+(a[i]-'0'))%MOD1;
if(i)
p1=(p1*BAZA)%MOD1;
}
if(n>m)
{
fo<<0;
fi.close();
fo.close();
return 0;
}
for(int i=0;i<n;i++)
rhash1=(rhash1*BAZA+(b[i]-'0'))%MOD1;
if(rhash1==val1)
v.push_back(0);
for(int i=n;i<m;i++)
{
rhash1=(((rhash1-(b[i-n]-'0')*p1)%MOD1+MOD1)*BAZA+(b[i]-'0'))%MOD1;
if(rhash1==val1)
v.push_back(i-n+1);
}
int sol=v.size();
fo<<sol<<"\n";
for(int i=0;i<min(sol,1000);i++)
fo<<v[i]<<" ";
fi.close();
fo.close();
return 0;
}