Pagini recente » Cod sursa (job #2967620) | Cod sursa (job #2644677) | Cod sursa (job #3038416) | Cod sursa (job #44030) | Cod sursa (job #3268158)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
using ll = long long;
const int mod=666063;
string s,p;
int n,m,val[200];
vector<int> ans;
int xlan(int x,int n)
{
if(n==0) return 1;
else
{
int p=xlan(x,n/2);
if(n%2==0) return 1LL*p*p%mod;
else return 1LL*p*p%mod*1LL*x%mod;
}
}
int init_hash(int fi,int se,string s)
{
ll ans=0;
for(int i=fi;i<se;i++)
ans=(ans*62+val[s[i]])%mod;
return ans%mod;
}
void init_val()
{
int v=-1;
for(int i='a';i<='z';i++)
val[i]=++v;
for(int i='A';i<='Z';i++)
val[i]=++v;
for(int i='0';i<='9';i++)
val[i]=++v;
}
bool egale(string a,string b)
{
if(a.size()!=b.size()) return 0;
for(int i=0;i<a.size();i++)
if(a[i]!=b[i]) return 0;
return 1;
}
int main()
{
cin>>p>>s;
n=size(s);
m=size(p);
init_val();
ll q=xlan(62,m-1);
ll hp=init_hash(0,m,p);
ll hs=init_hash(0,m,s);
for(int i=0;i<=n-m;i++)
{
if(hp==hs)
ans.push_back(i);
hs=hs+mod-(1LL*q*val[s[i]])%mod;
hs=hs*62%mod+val[s[i+m]]; hs%=mod;
}
cout<<ans.size()<<"\n";
for(int i=0;i<min(1000,(int)ans.size());i++)
cout<<ans[i]<<" ";
return 0;
}