Cod sursa(job #2452028)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 29 august 2019 11:24:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb

//Rabin-Karp

#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define fs first
#define sc second
#define pii pair <int, int>
#define Nmax 2000005
#define MOD1 666013
#define MOD2 100007

using namespace std;

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

char a[Nmax], b[Nmax];
int ha1, ha2;
int hb1, hb2;
queue <int> Q;
int ans, p1=1, p2=1;

int main()
{
    f >> a >> b;
    int la=strlen(a), lb=strlen(b);

    if (la > lb)
    {
        g << "0";
        return 0;
    }

    for (int i = 0; i < la; i++)
    {
        ha1 = ha1 * 73 + a[i]; ha1 %= MOD1;
        ha2 = ha2 * 73 + a[i]; ha2 %= MOD2;
        hb1 = hb1 * 73 + b[i]; hb1 %= MOD1;
        hb2 = hb2 * 73 + b[i]; hb2 %= MOD2;
        if (i != 0)
        {
            p1 = p1 * 73; p1 %= MOD1;
            p2 = p2 * 73; p2 %= MOD2;
        }
    }

    if (ha1 == hb1 && ha2 == hb2)
    {
        ans++;
        Q.push(0);
    }

    for (int i = la; i < lb; i++)
    {
        hb1 = ((hb1 - (p1*b[i-la])%MOD1 + MOD1) % MOD1) * 73 + b[i]; hb1%=MOD1;
        hb2 = ((hb2 - (p2*b[i-la])%MOD2 + MOD2) % MOD2) * 73 + b[i]; hb2%=MOD2;

        if (hb1 == ha1 && ha2 == hb2)
        {
            ans++;
            if (Q.size() < 1000) Q.push(i-la+1);
        }
    }
    g << ans << '\n';
    while (!Q.empty())
    {
        g << Q.front() << " ";
        Q.pop();
    }

    return 0;
}