Cod sursa(job #1402083)

Utilizator EpictetStamatin Cristian Epictet Data 26 martie 2015 12:20:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <string>
#include <vector>
#define MOD1 200003
#define MOD2 200009
#define P 73
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A, B;
vector < int > V;
int h1_A, h2_A, h1_B, h2_B, sol, P1, P2;

void Verif(int p)
{
    if (h1_A == h1_B && h2_A == h2_B) {
        sol++;
        V.push_back(p);
    }
}

void Write_Data()
{
    fout << sol << '\n';
    for (auto it : V) {
        fout << it << ' ';
    }
    fout.close();
}

int main()
{
    fin >> A >> B;
    P1 = P2 = 1;
    for (int i = 0; i < A.size(); i++)
    {
        h1_A = (h1_A * P + A[i]) % MOD1;
        h2_A = (h2_A * P + A[i]) % MOD2;

        if (i) {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }

        h1_B = (h1_B * P + B[i]) % MOD1;
        h2_B = (h2_B * P + B[i]) % MOD2;
    }

    Verif(0);
    for (int i = A.size(); i < B.size(); i++)
    {
        h1_B = (((h1_B - (P1 * B[i - A.size()])) % MOD1 + MOD1) * P + B[i]) % MOD1;
        h2_B = (((h2_B - (P2 * B[i - A.size()])) % MOD2 + MOD2) * P + B[i]) % MOD2;
        Verif(i - A.size() + 1);
    }

    Write_Data();
    return 0;
}