Cod sursa(job #2573143)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 5 martie 2020 16:01:15
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");

ofstream fout("strmatch.out");



#define NMAX 2000001



#define mod 666023





string a,b;



int m,n;



long long po[NMAX];



vector<int> occ;



void rabin_karp(string const& s, string const& t) {

    const int p = 73;

    const int m = 666023;

    int S = s.size(), T = t.size();



    vector<long long> p_pow(max(S, T));

    p_pow[0] = 1;



    for (int i = 1; i < (int)p_pow.size(); i++)

        p_pow[i] = (p_pow[i-1] * p) % m;



    vector<long long> h(T + 1, 0);



    for (int i = 0; i < T; i++)

    {

       if(isupper(t[i]))

         h[i+1] = (h[i] + (t[i] - 'A' + 1) * p_pow[i]) % m;

      else if(islower(t[i]))

         h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;

      else

         h[i+1] = (h[i] + (t[i] - '0' + 1) * p_pow[i]) % m;

    }





    long long h_s = 0;



    for (int i = 0; i < S; i++)

   {

      if(isupper(s[i]))

         h_s = (h_s + (s[i] - 'A' + 1) * p_pow[i]) % m;

      else if(islower(s[i]))

         h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;

      else

         h_s = (h_s + (s[i] - '0' + 1) * p_pow[i]) % m;

   }



    vector<int> occurences;

    for (int i = 0; i + S - 1 < T; i++) {

        long long cur_h = (h[i+S] + m - h[i]) % m;

        if (cur_h == h_s * p_pow[i] % m)

            occurences.push_back(i);

    }



    fout<<occurences.size()<<'\n';
      int nr = 0;
      for(int i=0;i<occurences.size() && nr < 1000;i++)
      {
         fout<<occurences[i]<<" ";
         nr++;
      }


}



int main()
{


   fin>>a>>b;




   if(a.size() > b.size())

   {

      fout<<0;

      return 0;

   }

   else

   {

      rabin_karp(a,b);

   }



   return 0;

}