Cod sursa(job #2730943)

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

using namespace std;

const int prime1 = 666013;
const int prime2 = 666067;
string verif;

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

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

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

    return 0;
}