Pagini recente » Cod sursa (job #1874325) | Cod sursa (job #359829) | Cod sursa (job #2927983) | Cod sursa (job #3293240) | Cod sursa (job #3216168)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MOD=1e9+7;
const int MOD2=1e9+9;
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()
{
fin >>a>>b;
if (a.size ()>b.size ()){
fout <<0;
return 0;
}
p=expr (26,a.size ()-1,MOD);
p2=expr (26,a.size ()-1,MOD2);
for (int i=0;i<a.size ();++i){
coda*=26;
coda+=a[i]-'A';
coda%=MOD;
coda2*=26;
coda2+=a[i]-'A';
coda2%=MOD2;
}
for (int i=0;i<b.size ();++i){
if (i<a.size ()){
codb*=26;
codb+=b[i]-'A';
codb%=MOD;
codb2*=26;
codb2+=b[i]-'A';
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 ()]-'A')%MOD);
if (codb<0) codb+=MOD;
codb2-=(p*(b[i-a.size ()]-'A')%MOD2);
if (codb2<0) codb2+=MOD2;
codb*=26;
codb+=b[i]-'A';
codb%=MOD;
codb2*=26;
codb2+=b[i]-'A';
codb2%=MOD2;
}
}
fout <<nr<<'\n';
for (int i=0;i<rez.size ();++i) fout <<rez[i]<<' ';
return 0;
}