Pagini recente » Cod sursa (job #1089540) | Cod sursa (job #1939469) | Cod sursa (job #2453919) | Cod sursa (job #138020) | Cod sursa (job #2281846)
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const string FILENAME="strmatch";
#define OpenIN() freopen((FILENAME+".in").c_str(),"r",stdin)
#define OpenOUT() freopen((FILENAME+".out").c_str(),"w",stdout)
#define OpenALL() OpenIN(), OpenOUT()
#define infoarena() OpenALL()
const int MOD=1000000007;
const int N=2000000+5;
const int BAZE=47;
inline int add(int a,int b)
{
a+=b;
if(a>=MOD)
{
a-=MOD;
}
if(a<0)
{
a+=MOD;
}
return a;
}
inline int mul(int a,int b)
{
return a*(long long)b%MOD;
}
inline int expow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)
{
ans=mul(ans,a);
}
a=mul(a,a);
b>>=1;
}
return ans;
}
int p[N];
int inv[N];
int pre[N];
int ans[1005],cnt=0;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
infoarena();
p[0]=1;
for(int i=1;i<N;i++)
{
p[i]=mul(p[i-1],BAZE);
}
inv[N-1]=expow(p[N-1],MOD-2);
for(int i=N-2;i>=0;i--)
{
inv[i]=mul(inv[i+1],BAZE);
}
string pat;
string s;
cin>>pat>>s;
int m=pat.size();
int n=s.size();
pat="."+pat, s="."+s;
int PatMask=0;
for(int i=1;i<=m;i++)
{
PatMask=add(PatMask,mul(p[i-1],pat[i]-'A'));
}
for(int i=1;i<=n;i++)
{
pre[i]=add(pre[i-1],mul(p[i-1],s[i]-'A'));
}
for(int st=1;st+m-1<=n;st++)
{
int dr=st+m-1;
int value=add(pre[dr],-pre[st-1]);
value=mul(value,inv[st-1]);
if(value==PatMask)
{
cnt++;
if(cnt<=1000)
{
ans[cnt]=st-1;
}
}
}
cout<<cnt<<"\n";
cnt=min(cnt,1000);
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
return 0;
}