Cod sursa(job #1881690)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 16 februarie 2017 17:50:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

const ll NMax = 2000001;
const ll INF = 0x3f3f3f3f;
const ll mod1 = 666013;
const ll mod2 = 666041;

const ll a = 3;
const ll b = 10007;

char x[NMax],y[NMax];
ll hash1,hash2;
ll H1,H2;
vector<ll> ans;

int main()
{
    f.getline(x,NMax);
    f.getline(y,NMax);
    ll X = strlen(x);
    ll Y = strlen(y);

    ll A = 1,B = 1;
    for(ll i = X - 1; i >= 0; --i){
        if(i == X - 1){
            H1 = x[i];
            H2 = x[i];
            hash1 = y[i];
            hash2 = y[i];
            continue;
        }
        A *= a; B *= b; A %= mod1; B %= mod2;
        H1 = H1 + A * x[i]; H1 %= mod1;
        H2 = H2 + B * x[i]; H2 %= mod2;

        hash1 = hash1 + A * y[i]; hash1 %= mod1;
        hash2 = hash2 + B * y[i]; hash2 %= mod2;
    }
    for(ll i = X; i < Y; ++i){
        if(hash1 == H1 && hash2 == H2){
            ans.push_back(i - 1);
        }

        hash1 = (hash1 - (y[i - X] * A) % mod1 + mod1) % mod1;
        hash1 = hash1 * a; hash1 %= mod1;
        hash1 = hash1 + y[i]; hash1 %= mod1;

        hash2 = (hash2 - (y[i - X] * B) % mod2 + mod2) % mod2;
        hash2 = hash2 * b; hash2 %= mod2;
        hash2 = hash2 + y[i]; hash2 %= mod2;
    }
    if(hash1 == H1 && hash2 == H2){
        ans.push_back(Y - 1);
    }
    g << ans.size() << '\n';
    for(ll i = 0; i < ans.size(); ++i){
        g << ans[i] - X + 1 << ' ';
    }
    return 0;
}