Pagini recente » Cod sursa (job #2491031) | Cod sursa (job #2947912) | Cod sursa (job #1076041) | Cod sursa (job #2318133) | Cod sursa (job #3216166)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MOD=1e9+7;
typedef long long ll;
const int MAXN=2e6+10;
ll p;
ll expr (ll x, ll e){
if (e==0) return 1;
if (e%2==1) return x*expr (x,e-1)%MOD;
ll aux=expr (x,e/2);
return aux*aux%MOD;
}
string a,b;
ll coda,codb,nr;
vector <int> rez;
int main()
{
fin >>a>>b;
if (a.size ()>b.size ()){
fout <<0;
return 0;
}
p=expr (26,a.size ()-1);
for (int i=0;i<a.size ();++i){
coda*=26;
coda+=a[i]-'A';
coda%=MOD;
}
for (int i=0;i<b.size ();++i){
if (i<a.size ()){
codb*=26;
codb+=b[i]-'A';
codb%=MOD;
}
else{
if (codb==coda){
nr++;
if (nr<=1000)
rez.emplace_back (i-a.size ());
}
codb-=(p*(b[i-a.size ()]-'A')%MOD);
if (codb<0) codb+=MOD;
codb*=26;
codb+=b[i]-'A';
codb%=MOD;
}
}
fout <<nr<<'\n';
for (int i=0;i<rez.size ();++i) fout <<rez[i]<<' ';
return 0;
}