Pagini recente » Cod sursa (job #1009176) | Cod sursa (job #365525) | Cod sursa (job #261097) | Cod sursa (job #1053469) | Cod sursa (job #2457992)
#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=1e9+7,mod2=666013;
int main()
{
long long put751=1,put752=1;
cin>>s1>>s2;
for(int i=1;i<s1.size();i++){
put751*=75;
put752*=75;
put751%=mod1;
put752%=mod2;
}
for(int i=0;i<s1.size();i++){
nr160=((long long)nr160*75+(s1[i]-'0'+1))%mod2;
nr10=((long long)nr10*75+(s1[i]-'0'+1))%mod1;
}
for(int i=0;i<s1.size();i++){
nr260=((long long)nr260*75+(s2[i]-'0'+1))%mod2;
nr210=((long long)nr210*75+(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)*put752)*75+(s2[i]-'0'+1))%mod2 + mod2;
nr260%=mod2;
nr210=(((long long)nr210-(s2[i-s1.size()]-'0'+1)*put751)*75+(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;
}