Cod sursa(job #2147508)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 28 februarie 2018 19:51:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;

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

const int  LEN_MAX = 2000000;
const int MOD1 = 100003, MOD2 = 100019, BAZA = 74;

string a, b;

int nrAns, hA1, hA2;
vector<int> ansPoz;

void genHash()
{
    int p1 = 1, p2 = 1;
    for(int i = 1; i < a.length(); i++)
    {
        p1 = (p1 * BAZA) % MOD1;
        p2 = (p2 * BAZA) % MOD2;
    }

    int h1 = 0, h2 = 0;
    for(int i = 0; i < a.length(); i++)
    {
        h1 = (h1 * BAZA + b[i]) % MOD1;
        h2 = (h2 * BAZA + b[i]) % MOD2;
    }
    if(h1 == hA1 && h2 == hA2)
    {
        nrAns++;
        ansPoz.push_back(0);
    }

    int st = 0;
    for(int dr = a.length(); dr < b.length(); dr++)
    {
        h1 = (((h1 - p1 * b[st]) % MOD1 + MOD1) * BAZA + b[dr]) % MOD1;
        h2 = (((h2 - p2 * b[st]) % MOD2 + MOD2) * BAZA + b[dr]) % MOD2;

        st++;
        if(h1 == hA1 && h2 == hA2)
        {
            nrAns++;
            if(nrAns <= 1000)
                ansPoz.push_back(st);
        }
    }
}

int main()
{
    in >> a >> b;

    hA1 = hA2 = 0;
    for(int i = 0; i < a.length(); i++)
    {
        hA1 = (hA1 * BAZA + a[i]) % MOD1;
        hA2 = (hA2 * BAZA + a[i]) % MOD2;
    }

    genHash();

    vector<int>::iterator it;
    out << nrAns << '\n';
    for(it = ansPoz.begin(); it != ansPoz.end(); it++)
        out << *it << ' ';
    out << '\n';

    return 0;
}