Cod sursa(job #3002870)

Utilizator dariustgameTimar Darius dariustgame Data 15 martie 2023 11:55:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const long long mod = 1000007;
const long long baza = 30;
long long power = 1;


int hashh(string s)
{
    long long r = 0;
    for (long long i = 0; i < s.size(); i++)
    {
        r = r * baza + s[i];
        r %= mod;
    }
    return r;
}

vector<long long> poz;

void rabin_karp(string sir, string pat)
{
    long long cnt = 0;
    long long h1 = hashh(pat);
    long long h2 = 0;
    for (long long i = 0; i < pat.size(); i++)
    {
        power = (power * baza) % mod;
    }
    for (long long i = 0; i < sir.size(); i++)
    {
        h2 = h2 * baza + sir[i];
        h2 %= mod;
        if (i >= pat.size())
        {
            h2 -= (power * sir[i - pat.size()]) % mod;
            if (h2 < 0)
            {
                h2 += mod;
            }
        }
        if (i >= pat.size() - 1 && h1 == h2)
        {
            cnt++;
            poz.push_back(i - pat.size() + 1);
        }
    }
    fout << cnt << '\n';
    for (long long i = 0; i < poz.size(); i++)
    {
        fout << poz[i] << ' ';
    }
}


int main()
{
    string sir, pat;
    fin >> pat >> sir;
    rabin_karp(sir, pat);
    return 0;
}