Cod sursa(job #2015804)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 27 august 2017 15:49:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

#define MOD1 10007
#define MOD2 666013
using namespace std;

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

string A, B;
vector<int>pos;
const int base1 = 27, base2 = 29;

int hash1, hash2, HASH1, HASH2, answ;

int main()
{
    fin >> A; fin.get(); fin >> B;
    pos.resize(B.length() + 1, 0);


    int lengthA = A.length();
    int Pow1 = 1, Pow2 = 1;
    for (int i = 0; i < lengthA; ++i)
    {
        hash1 = (hash1 * base1 + A[i]) % MOD1;
        hash2 = (hash2 * base2 + A[i]) % MOD2;

        if (i)
            Pow1 = (Pow1 * base1) % MOD1, Pow2 = (Pow2 * base2) % MOD2;
    }

    if (lengthA > B.length())
    {
        fout << 0 << "\n";
        return 0;
    }

    for (int i = 0; i < A.length();)
        HASH1 = (HASH1 * base1 + B[i]) % MOD1, HASH2 = (HASH2 * base2 + B[i++]) % MOD2;

    if (hash1 == HASH1 && hash2 == HASH2)
        ++answ, pos[0] = 1;

    for (int i = lengthA; i < B.length(); ++i)
    {
        HASH1 = ((HASH1 - (B[i - lengthA] * Pow1) % MOD1 + MOD1) * base1 + B[i]) % MOD1;
        HASH2 = ((HASH2 - (B[i - lengthA] * Pow2) % MOD2 + MOD2) * base2 + B[i]) % MOD2;

        if (hash1 == HASH1 && hash2 == HASH2)
            ++answ, pos[i - lengthA + 1] = 1;

    }
    fout << answ << "\n";
    int cnt = 0;
    for (int i = 0; i < B.length() && cnt < 1000; ++i)
        if (pos[i])
            fout << i << " ", cnt++;

    return 0;
}