Pagini recente » Cod sursa (job #81204) | Cod sursa (job #2927674) | Cod sursa (job #427185) | Cod sursa (job #1866724) | Cod sursa (job #2930822)
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
string a,b;
int nr;
pair<int,int> pw[1000005];
vector <int> v;
const int mod1=1e9+7,mod2=1e9+9;
void putere_74(){
pw[0]={1,1};
for (int i=1;i<=1000000;i++){
pw[i].first=(1LL*74*pw[i-1].first)%mod1;
pw[i].second=(1LL*74*pw[i-1].second)%mod2;
}
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
fin>>a>>b;
putere_74();
pair<int,int> h,h2;
for (int i=0;i<a.size();i++){
h.first=(1LL*74*h.first+a[i]-'0')%mod1;
h.second=(1LL*74*h.second+a[i]-'0')%mod2;
}
for (int i=0;i<a.size()-1;i++){
h2.first=(1LL*74*h2.first+b[i]-'0')%mod1;
h2.second=(1LL*74*h2.second+b[i]-'0')%mod2;
}
for (int i=a.size()-1;i<b.size();i++){
h2.first=(1LL*74*h2.first+b[i]-'0')%mod1;
h2.second=(1LL*74*h2.second+b[i]-'0')%mod2;
if (h2==h){
nr++;
v.push_back(i-a.size()+1);
}
h2.first=(1LL*h2.first-((1LL*(b[i-a.size()+1]-'0')*pw[a.size()-1].first)%mod1)+mod1)%mod1;
h2.second=(1LL*h2.second-((1LL*(b[i-a.size()+1]-'0')*pw[a.size()-1].second)%mod2)+mod2)%mod2;
}
fout<<nr<<"\n";
for (int i=0;i<min(nr,1000);i++)
fout<<v[i]<<" ";
}