Cod sursa(job #2669817)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 8 noiembrie 2020 00:59:38
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>

using namespace std;

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

string s, pattern;

vector < int > pos;

void RabinKarp(string s, string pattern, vector < int > &pos)
{
    const int base = 256;
    const int mod = 2000000011;

    int n = s.size();
    int m = pattern.size();

    int p = 1;
    int hs = 0, hpattern = 0;
    for (int i=0; i<m; i++)
    {
        hs = (1LL * hs * base + s[i]) % mod;
        hpattern = (1LL * hpattern * base + pattern[i]) % mod;
        if (i > 0)
            p = (1LL * p * base) % mod;
    }

    if (hs == hpattern && pattern.compare(0, m, s, 0, m) == 0)
        pos.push_back(0);

    for (int i=m; i<n; i++)
    {
        hs = (((1LL * hs + mod - (1LL * p * s[i-m]) % mod) * base) + s[i]) % mod;
        if (hs == hpattern && pattern.compare(0, m, s, i-m+1, m) == 0)
            pos.push_back(i-m+1);
    }
}

int main()
{
    f >> pattern >> s;

    RabinKarp(s, pattern, pos);

    int n = pos.size();

    g << n << "\n";

    n = min(n, 1000);

    for (int i=0; i<n; i++)
        g << pos[i] << " ";

    return 0;
}