Pagini recente » Cod sursa (job #2421403) | Monitorul de evaluare | Cod sursa (job #915118) | Cei mai harnici utilizatori info-arena | Cod sursa (job #2258881)
#include <bits/stdc++.h>
using namespace std;
const int N=2000000+5;
const int MOD=1000000007;
inline int f(char ch)
{
if('a'<=ch && ch<='z')
return ch-'a';
return ch-'A'+'z'-'a'+1;
}
inline int mul(int a,int b)
{
return a*(long long)b%MOD;
}
inline int add(int a,int b)
{
a+=b;
if(a>=MOD)
a-=MOD;
if(a<0)
a+=MOD;
return a;
}
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;
}
string caut,a;
int m,n;
int inv[N];
int sr[N];
inline int get(int st,int dr)
{
if(st==0)
return sr[dr];
int dif=add(sr[dr],-sr[st-1]);
return mul(dif,inv[st]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","r",stdin);
cin>>caut>>a;
m=caut.size();
n=a.size();
int p=expow(52,N-1);
inv[N-1]=expow(p,MOD-2);
for(int i=N-2;i>=0;i--)
inv[i]=mul(inv[i+1],52);
int need=0;
for(int i=0;i<m;i++)
{
need=add(need,mul(expow(52,i),f(caut[i])));
}
int val=0;
for(int i=0;i<n;i++)
{
val=add(val,mul(expow(52,i),f(a[i])));
sr[i]=val;
}
int ans=0;
vector<int>a;
for(int i=0;i+m-1<n;i++)
if(get(i,i+m-1)==need)
{
ans++;
if(a.size()<1000)
a.push_back(i);
}
cout<<ans<<"\n";
for(auto x:a)
cout<<x<<" ";
cout<<"\n";
return 0;
}