Cod sursa(job #2572855)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 5 martie 2020 14:37:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define NMAX 805

#define mod 666023
#define p 73


char a[NMAX];
char b[NMAX];

int m,n;

long long po[NMAX];

vector<int> occ;

void rubin(char a[],char b[])
{
   long long curr_h = 0;
   int siz = max(n,m);
   vector<int> hash(siz+1,0);

   po[0] = 1;
   for(int i=1;i<=siz;i++)
   {
      po[i] = (po[i-1] * p ) % mod;
   }

   //for(int i=1;i<=n;i++)
      //cout<<hash[i]<<" ";

   for(int i=0;i<m;i++)
   {
      if(a[i] >= 'A' && a[i]<= 'Z')
      {
         curr_h = (curr_h + (a[i]-'A'+1) * po[i] ) % mod;
      }
      else if(a[i] >= 'a' && a[i]  <= 'z')
      {
         curr_h = (curr_h + (a[i]-'a'+1) * po[i] ) % mod;
      }
      else
         curr_h = (curr_h + (a[i]-'0'+1) * po[i] ) % mod;
   }

   for(int i=0;i<n;i++)
   {
      if(b[i] >= 'A' && b[i]<= 'Z')
      {
         hash[i+1] = (hash[i] + (b[i]-'A'+1)*po[i] ) % mod;
      }
      else if(b[i] >= 'a' && b[i]  <= 'z')
      {
         hash[i+1] = (hash[i] + (b[i]-'a'+1)*po[i] ) % mod;
      }
      else
         hash[i+1] = (hash[i] + (b[i]-'0'+1)*po[i] ) % mod;
   }


   for(int i=0;i<n-m+1 && occ.size() < 1001;i++)
   {
      long long h = (hash[i+m]-hash[i] + mod) % mod;
      if(h == (curr_h * po[i]) % mod )
         occ.push_back(i);

   }


}

int main()
{

   fin.getline(a,NMAX);
   fin.getline(b,NMAX);

   m = strlen(a);
   n = strlen(b);

   if(m>n)
   {
      fout<<0;
      return 0;
   }
   else
   {

      rubin(a,b);
      fout<<occ.size()<<'\n';
      for(int i=0;i<occ.size();i++)
         fout<<occ[i]<<" ";
   }

   return 0;
}