Cod sursa(job #3305995)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 6 august 2025 14:16:56
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
//cu hash
#include <fstream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
unsigned int hashes[2000005], base=257;
unsigned int powar[2000005];

void buildh( string b){
    unsigned int n=b.size();
    for(unsigned int i=n;i>=1;i--){
        hashes[i]=(hashes[i+1]*base + b[i-1]);
    }
}
void buildp(string b){
   unsigned int n=b.size();
   powar[0]=1;
   for(unsigned int i=1;i<=n;i++){
       powar[i]=powar[i-1]*base;
   }
}
unsigned int buildpathash(string a){
   unsigned int n=a.size() , hashs=0;
   for(unsigned int i=n;i>=1;i--){
      hashs=hashs*base+a[i-1];
   }
   return hashs;
}
unsigned int buildbhash(unsigned int lf , unsigned int rg){
  return ( hashes[lf]- hashes[rg+1]* powar[rg-lf+1]);
}
bool patmatch ( unsigned int hashs, unsigned int lf , unsigned int rg){
   return hashs==buildbhash(lf,rg);
}
int main(){
   string a,b;
   cin>>a>>b;
   buildh(b);
   buildp(b);

   unsigned int hashs= buildpathash(a) , cnt=0;
   for(unsigned int i=1;i+a.size()-1 <=b.size();i++){
      if(patmatch(hashs,i,i+a.size()-1)) cnt++;
   }

   cout<<cnt<<endl;
   unsigned int asize, bsize;
   asize=a.size();
   bsize=b.size();
   for(unsigned int  j=1;j+asize-1<=bsize;j++){
       if(cnt<1000 && patmatch(hashs,j,j+asize-1)){
         cnt++;
         cout<<j-1<<" ";
       }
   }
}