Pagini recente » Cod sursa (job #2118656) | Cod sursa (job #1946418) | Cod sursa (job #1439483) | Cod sursa (job #1722103) | Cod sursa (job #3216207)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MOD=100007;
const int MOD2=100021;
const int B=255;
typedef long long ll;
const int MAXN=2e6+10;
ll p,p2;
ll expr (ll x, ll e, ll m){
if (e==0) return 1;
if (e%2==1) return x*expr (x,e-1,m)%m;
ll aux=expr (x,e/2,m);
return aux*aux%m;
}
string a,b;
ll coda,codb,nr,coda2,codb2;
vector <int> rez;
int main()
{
//fout <<int ('Z');
fin >>a>>b;
if (a.size ()>b.size ()){
fout <<0;
return 0;
}
p=expr (B,a.size ()-1,MOD);
p2=expr (B,a.size ()-1,MOD2);
for (int i=0;i<a.size ();++i){
coda*=B;
coda+=a[i];
coda%=MOD;
coda2*=B;
coda2+=a[i];
coda2%=MOD2;
}
for (int i=0;i<b.size ();++i){
if (i<a.size ()){
codb*=B;
codb+=b[i];
codb%=MOD;
codb2*=B;
codb2+=b[i];
codb2%=MOD2;
}
else{
if (codb==coda and coda2==codb2){
nr++;
if (nr<=1000)
rez.emplace_back (i-a.size ());
}
codb-=(p*(b[i-a.size ()])%MOD);
if (codb<0) codb+=MOD;
codb2-=(p2*(b[i-a.size ()])%MOD2);
if (codb2<0) codb2+=MOD2;
codb*=B;
codb+=b[i];
codb%=MOD;
codb2*=B;
codb2+=b[i];
codb2%=MOD2;
}
}
if (codb==coda and coda2==codb2){
nr++;
if (nr<=1000)
rez.emplace_back (b.size ()-a.size ());
}
fout <<nr<<'\n';
for (int i=0;i<rez.size ();++i) fout <<rez[i]<<' ';
return 0;
}