Pagini recente » Cod sursa (job #3368944) | Cod sursa (job #3368935) | Cod sursa (job #3368908) | Cod sursa (job #3368940) | Cod sursa (job #3368930)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main()
{
string a,b;
fin>>a>>b;
int n=a.size();
int m=b.size();
if(n>m) {
fout<<0<<"\n\n";
return 0;
}
long long ha=0,hb=0,p=1;
int mod=123456791;
for(int i=0; i<n; i++) {
ha=(ha*37+a[i])%mod;
hb=(hb*37+b[i])%mod;
if(i<n-1) {
p=p*37%mod;
}
}
int cnt=0;
vector<int> poz;
for(int i=0; i<=m-n; i++) {
if(ha==hb&& b.compare(i,n,a)==0) {
cnt++;
if(poz.size()<1000)
poz.push_back(i);
}
if(i<m-n) {
hb=(hb-b[i]*p%mod+mod)%mod;
hb=(hb*37+b[i+n])%mod;
}
}
fout<<cnt<<'\n';
for(int x:poz) {
fout<<x<<' ';
}
return 0;
}