Cod sursa(job #2558417)

Utilizator TheRealInfiniteConstantin Alexandru TheRealInfinite Data 26 februarie 2020 16:05:39
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

#define MOD1 100007
#define MOD2 100021

#define d 256

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

void RabinKarp(string pattern, string text)
{
    int pLenght = pattern.size();
    int tLenght = text.size();

    int p1 = 0;
    int p2 = 0;
    int t1 = 0;
    int t2 = 0;

    int dL1 = 1;
    int dL2 = 1;

    int cnt = 0;

    vector<int> positions;

    for(int i = 1; i < pLenght; i++)
    {
        dL1 = (dL1 * d) % MOD1;
        dL2 = (dL2 * d) % MOD2;
    }

    for(int i = 0; i < pLenght; i++)
    {
        p1 = (d * p1 + pattern[i]) % MOD1;
        p2 = (d * p2 + pattern[i]) % MOD2;

        t1 = (d * t1 + text[i]) % MOD1;
        t2 = (d * t2 + text[i]) % MOD2;
    }


    for(int i = 0; i < tLenght - pLenght && cnt < 1000; i++)
    {
        if(p1 == t1 && p2 == t2)
        {
            cnt++;

            positions.push_back(i);
        }

        t1 = (d * (t1 - text[i] * dL1) + text[i + pLenght]) % MOD1;
        t2 = (d * (t2 - text[i] * dL2) + text[i + pLenght]) % MOD2;

        if(t1 < 0) t1 += MOD1;
        if(t2 < 0) t2 += MOD2;
    }

    g<<cnt<<endl;

    for(int i = 0; i < positions.size(); i++)
        g<<positions[i]<<" ";

}

int main()
{
    string pattern;
    string text;

    f>>pattern;
    f>>text;

    RabinKarp(pattern, text);

}