Pagini recente » Cod sursa (job #2167656) | Cod sursa (job #1466664) | Cod sursa (job #3243150) | Cod sursa (job #1140928) | Cod sursa (job #2930818)
#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_57(){
pw[0]={1,1};
for (int i=1;i<=1000000;i++){
pw[i].first=(1LL*57*pw[i-1].first)%mod1;
pw[i].second=(1LL*57*pw[i-1].second)%mod2;
}
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
fin>>a>>b;
putere_57();
pair<int,int> h,h2;
for (int i=0;i<a.size();i++){
h.first=(1LL*57*h.first+a[i]-'A')%mod1;
h.second=(1LL*57*h.second+a[i]-'A')%mod2;
}
for (int i=0;i<a.size()-1;i++){
h2.first=(1LL*57*h2.first+b[i]-'A')%mod1;
h2.second=(1LL*57*h2.second+b[i]-'A')%mod2;
}
for (int i=a.size()-1;i<b.size();i++){
h2.first=(1LL*57*h2.first+b[i]-'A')%mod1;
h2.second=(1LL*57*h2.second+b[i]-'A')%mod2;
if (h2==h){
nr++;
v.push_back(i-a.size()+1);
}
h2.first=(1LL*h2.first-((1LL*(b[i-a.size()+1]-'A')*pw[a.size()-1].first)%mod1)+mod1)%mod1;
h2.second=(1LL*h2.second-((1LL*(b[i-a.size()+1]-'A')*pw[a.size()-1].second)%mod1)+mod1)%mod1;
}
fout<<nr<<"\n";
for (int i=0;i<min(nr,1000);i++)
fout<<v[i]<<" ";
}