Cod sursa(job #3004095)

Utilizator dariustgameTimar Darius dariustgame Data 16 martie 2023 09:46:32
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 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)
        {
            bool ok = true;
            for (int j = 0; j < pat.size(); j++)
            {
                if (sir[i - j] != pat[j])
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
            {
                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;
}