Pagini recente » Cod sursa (job #1301359) | Istoria paginii utilizator/baitan_bianca | Cod sursa (job #761653) | Cod sursa (job #1911983) | Cod sursa (job #2457985)
#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()
{
long long put75=1;
cin>>s1>>s2;
for(int i=1;i<s1.size();i++){
put75*=75;
}
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)*put75)*75+(s2[i]-'0'+1))%mod2 + mod2;
nr260%=mod2;
nr210=(((long long)nr210-(s2[i-s1.size()]-'0'+1)*put75)*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;
}