Cod sursa(job #2792116)

Utilizator un_fes_galbendaniel guba un_fes_galben Data 31 octombrie 2021 23:07:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.73 kb
#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;
}