Pagini recente » Cod sursa (job #196324) | Cod sursa (job #3159769) | Cod sursa (job #1301333) | Cod sursa (job #834750) | Cod sursa (job #2457983)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s1,s2;
vector<int >a;
long long nr160,nr10,nr260,nr210;
const long long mod1=10e9+7,mod2=666013;
int main()
{
int put73=1;
cin>>s1>>s2;
for(int i=1;i<s1.size();i++){
put73*=73;
}
for(int i=0;i<s1.size();i++){
nr160=((long long)nr160*73+(s1[i]-'0'+1))%mod2;
nr10=((long long)nr10*73+(s1[i]-'0'+1))%mod1;
}
for(int i=0;i<s1.size();i++){
nr260=((long long)nr260*73+(s2[i]-'0'+1))%mod2;
nr210=((long long)nr210*73+(s2[i]-'0'+1))%mod1;
}
if((nr160==nr260) && (nr10==nr210))
a.push_back(0);
for(int i=s1.size();i<s2.size();i++){
nr260=(((long long)nr260-(s2[i-s1.size()]-'0'+1)*put73)*73+(s2[i]-'0'+1))%mod2 + mod2;
nr260%=mod2;
nr210=(((long long)nr210-(s2[i-s1.size()]-'0'+1)*put73)*73+(s2[i]-'0'+1))%mod1 + mod1;
nr210%=mod1;
if((nr10==nr210) && (nr160==nr260))
a.push_back(i-s1.size()+1);
}
cout<<a.size()<<'\n';
for(int i=0;i<min(1000,(int)a.size());i++)
cout<<a[i]<<" ";
return 0;
}