Cod sursa(job #1881711)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 16 februarie 2017 18:08:00
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

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

const int NMax = 2000001;
const int INF = 0x3f3f3f3f;
const int mod1 = 100007;
const int mod2 = 100021;

const int a = 73;
const int b = 7;

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

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

    int A = 1,B = 1;
    for(int 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;
    }
    int T = 0;
    for(int i = X; i < Y; ++i){
        if(hash1 == H1 && hash2 == H2){
            T++;
            if(ans.size() < 1000)
                ans.push_back(i - 1);
        }

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

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