Pagini recente » Cod sursa (job #729205) | Cod sursa (job #3038954) | Cod sursa (job #2274422) | Cod sursa (job #1749213) | Cod sursa (job #2792116)
#include <fstream>
using namespace std;
#define baza1 105
#define mod1 131072
#define baza2 157
#define mod2 66986
int p1,p2,val,nr;int precalc1[105],precalc2[105];short valpoz[2000005];
inline int CHash1(int poz1,int poz2,const string& s){
int h=0,i;
for(i=poz1;i<=poz2;i++){
if(s[i]>='0'&&s[i]<='9'){h=(h*baza1+s[i]-'0')%mod1;}
else if(s[i]>='a'&&s[i]<='z'){h=(h*baza1+s[i]-'a'+10)%mod1;}
else if(s[i]>='A'&&s[i]<='Z'){h=(h*baza1+s[i]-'A'+36)%mod1;}
}
return h;
}
inline int CHash2(int poz1,int poz2,const string& s){
int h=0,i;
for(i=poz1;i<=poz2;i++){
if(s[i]>='0'&&s[i]<='9'){h=(h*baza2+s[i]-'0')%mod2;}
else if(s[i]>='a'&&s[i]<='z'){h=(h*baza2+s[i]-'a'+10)%mod2;}
else if(s[i]>='A'&&s[i]<='Z'){h=(h*baza2+s[i]-'A'+36)%mod2;}
}
return h;
}
inline int AHash1(int poz,int valx){
val=valx;val=(val*baza1+valpoz[poz])%mod1;
return val;
}
inline int AHash2(int poz,int valx){
val=valx;val=(val*baza2+valpoz[poz])%mod2;
return val;
}
inline int EHash1(int poz,int valx){
val=valx;val=(mod1+val-precalc1[valpoz[poz]])%mod1;
return val;
}
inline int EHash2(int poz,int valx){
val=valx;val=(mod2+val-precalc2[valpoz[poz]])%mod2;
return val;
}
inline long long lgput1(long long baza,long long exp){
long long rez=1;int i;
for(i=exp;i>=1;i>>=1){
if(i&1){
rez*=baza;rez%=mod1;
}
baza*=baza;baza%=mod1;
}
return rez;
}
inline long long lgput2(long long baza,long long exp){
long long rez=1;int i;
for(i=exp;i>=1;i>>=1){
if(i&1){
rez*=baza;rez%=mod2;
}
baza*=baza;baza%=mod2;
}
return rez;
}
int var1,var2;int rez[1005];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;fin>>a>>b;int i,var3=0,var4=0,prez=1,cnt=0;p1=1;p2=1;
for(i=0;i<b.size();i++){
if(b[i]>='0'&&b[i]<='9'){valpoz[i]=b[i]-'0';}
else if(b[i]>='a'&&b[i]<='z'){valpoz[i]=b[i]-'a'+10;}
else if(b[i]>='A'&&b[i]<='Z'){valpoz[i]=b[i]-'A'+36;}
}
var1=CHash1(0,a.size()-1,a);var2=CHash2(0,a.size()-1,a);
p1=lgput1(baza1,a.size()-1);p2=lgput2(baza2,a.size()-1);
for(i=0;i<=80;i++){precalc1[i]=(i*p1)%mod1;precalc2[i]=(i*p2)%mod2;}
if(a.size()>=2){var3=CHash1(0,a.size()-2,b);var4=CHash2(0,a.size()-2,b);}
for(i=a.size()-1;i<b.size();i++){
var3=AHash1(i,var3);var4=AHash2(i,var4);
if(var3==var1&&var4==var2){
cnt++;if(prez<=1000){rez[prez]=i-a.size()+1;prez++;}
}
var3=EHash1(i-a.size()+1,var3);var4=EHash2(i-a.size()+1,var4);
}
fout<<cnt<<'\n';
for(i=1;i<prez;i++){fout<<rez[i]<<" ";}fout<<'\n';
return 0;
}