Cod sursa(job #2730945)

Utilizator TonioAntonio Falcescu Tonio Data 27 martie 2021 02:21:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

const int prime1 = 666013;
const int prime2 = 666067;
const int baza = 73;
char verif[2000001], subs[2000001], s[2000001];

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

void gaseste(char subs[], char s[])
{
    int nSubs = strlen(subs);
    int nS = strlen(s);
    int hashSubs1 = 0, putere1 = 1;
    int hashSubs2 = 0, putere2 = 1;
    for(int i = 0; i < nSubs; i++)
    {
        hashSubs1 = (baza * hashSubs1 + subs[i]) % prime1;
        hashSubs2 = (baza * hashSubs2 + subs[i]) % prime2;
        if(i)
        {
            putere1 = (putere1 * baza) % prime1;
            putere2 = (putere2 * baza) % prime2;
        }
    }
    int hashS1 = 0;
    int hashS2 = 0;
    for(int i = 0; i < nSubs; i++)
    {
        hashS1 = (baza * hashS1 + s[i]) % prime1;
        hashS2 = (baza * hashS2 + s[i]) % prime2;
    }
    int ans = 0;
    if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
    {
        verif[0] = 1;
        ans++;
    }
    for(int i = nSubs; i < nS; i++)
    {
        hashS1 = ((hashS1 - (s[i - nSubs] * putere1) % prime1 + prime1) * baza + s[i]) % prime1;
        hashS2 = ((hashS2 - (s[i - nSubs] * putere2) % prime2 + prime2) * baza + s[i]) % prime2;
        if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
        {
            verif[i - nSubs + 1] = 1;
            ans++;
        }
    }
    out << ans << "\n";
    for(int i = 0; i < nS; i++)
       if(verif[i])
            out << i << " ";
}

int main()
{
in >> subs;
in >> s;
gaseste(subs, s);

    return 0;
}