Cod sursa(job #2572907)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 5 martie 2020 14:51:49
Problema Potrivirea sirurilor Scor 38
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 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 && occurences.size() < 1001; 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';
      for(int i=0;i<occurences.size();i++)
         fout<<occurences[i]<<" ";

}

int main()
{

   fin>>a>>b;

   cout<<a<<" "<<b;

   if(a.size() > b.size())
   {
      fout<<0;
      return 0;
   }
   else
   {
      rabin_karp(a,b);
   }

   return 0;
}