Cod sursa(job #2536045)

Utilizator TheRealInfiniteConstantin Alexandru TheRealInfinite Data 1 februarie 2020 14:03:25
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

long long n, m;
long long mod1, mod2;
string A, B;

vector<long long> v;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

long long nr;

void RabinKarp()
{
  long long amod1=0, amod2=0;
  long long bmod1=0, bmod2=0;

  for(long long i = 0; i < m; i++)
  {
    bmod1 = (long long)(bmod1 * 53 + (B[i]-'a'+1)) % mod1;
    bmod2 = (long long)(bmod2 * 53 + (B[i]-'a'+1)) % mod2;
  }

  for(long long i = 0; i < m; i++)
  {
    amod1 = (long long)(amod1 * 53 + (A[i]-'a'+1)) % mod1;
    amod2 = (long long)(amod2 * 53 + (A[i]-'a'+1)) % mod2;
  }

  if(amod1 == bmod1 && amod2 == bmod2)
  {
    nr++;
    v.push_back(0);
  }

  long long p1=1;

  for(long long i = 1; i < m; i++)
    p1 = (long long)(p1 * 53) % mod1;

  long long p2=1;

  for(long long i = 1; i < m; i++)
    p2 = (long long)(p2 * 53) % mod2;

  for(long long i = m; i < n; i++)
  {
    amod1 = (long long)(((amod1 - p1 * (A[i - m]-'a'+1)) * 53 + (A[i]-'a'+1)) % mod1 + mod1) % mod1;
    amod2 = (long long)(((amod2 - p2 * (A[i - m]-'a'+1)) * 53 + (A[i]-'a'+1)) % mod2 + mod2) % mod2;
    if(amod1 == bmod1 && amod2 == bmod2)
    {
        nr++;
        v.push_back(i);
        if(nr == 1000)
            break;
    }
  }
}

int main()
{
  f>>B;
  f>>A;
  n = A.size();
  m = B.size();

  mod1 = 666013;
  mod2 = 1000000007;

  RabinKarp();

  g<<nr<<endl;
  for(long long i = 0; i < nr; i++)
      g<<(v[i] - m + 1)<<" ";

}