Cod sursa(job #1967112)

Utilizator TimoteiCopaciu Timotei Timotei Data 15 aprilie 2017 21:44:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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 mod 67
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 it_match(int x, int y)
{
    FOR(i, x, y)
     if(A[i - x] != B[i]) {
        cout << i << ' ';
        return 0;
     }
     return 1;
}
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int m, n, base = 63, p = 1, a = 0, b = 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){
      a = (base * a + v[int(A[i])]) % mod;
      b = (base * b + v[int(B[i])]) % mod;
      p *= base;
    }
    p /= base;
    FOR(i, 0, n - m){
      if(a == b && it_match(i, i + m)) sol.pb(i);
        b = ((b - (v[B[i]] * p) % mod + mod) * base + v[B[i + m + 1]]) % mod;
    }
    fout << sol.sz() << '\n';
    int x = sol.sz() - 1;
    if(sol.sz() != 0)
    FOR(i, 0, min(x, 999))
      fout << sol[i] << ' ';
    return 0;
}