Cod sursa(job #1967141)

Utilizator TimoteiCopaciu Timotei Timotei Data 15 aprilie 2017 22:32:28
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define FORR(i, x, y) for(int i = x; i >= y; --i)
#define pb(x) push_back(x)
#define sz() size()
#define mod1 67
#define mod2 71
using namespace std;
int v[130];
string A, B;
void set_poz()
{
   int nr = 0;
   FOR(i, 48, 57)
     v[i] = ++nr;
   FOR(i, 65, 90)
     v[i] = ++nr;
   FOR(i, 97, 122)
     v[i] = ++nr;
}
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int m, n, base = 63, p1 = 1, p2 = 1, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
    vector <int> sol;
    set_poz();
    fin >> A >> B;
    m = A.sz() - 1;
    n = B.sz() - 1;
    if(n < m){
        fout << 0;
        return 0;
    }
    FOR(i, 0, m){
      a1 = (base * a1 + v[int(A[i])]) % mod1;
      b1 = (base * b1 + v[int(B[i])]) % mod1;
      a2 = (base * a2 + v[int(A[i])]) % mod2;
      b2 = (base * b2 + v[int(B[i])]) % mod2;
      if(i != 0){
        p1 = (base * p1) % mod1;
        p2 = (base * p2) % mod2;
      }
    }
    FOR(i, 0, n - m){
      if(a1 == b1 && a2 == b2) sol.pb(i);
      b1 = ((b1 - (v[int(B[i])] * p1) % mod1 + mod1) * base + v[int(B[i + m + 1])]) % mod1;
      b2 = ((b2 - (v[int(B[i])] * p2) % mod2 + mod2) * base + v[int(B[i + m + 1])]) % mod2;
    }
    fout << sol.sz() << '\n';
    int x = sol.sz() - 1;
    if(sol.sz() != 0)
    FOR(i, 0, min(x, 999))
      fout << sol[i] << ' ';
    return 0;
}