Cod sursa(job #2536071)

Utilizator ViAlexVisan Alexandru ViAlex Data 1 februarie 2020 14:29:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include<bits/stdc++.h>
using namespace std;

#define MOD1 100007
#define MOD2 100021
#define MAX 74


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

string text,pattern;

void read()
{
    in>>pattern>>text;
}


void rabin_karp()
{
    int base1=1,base2=1;
    long long basemod1=0,basemod2=0;

    vector<int> results;

    for(int i=0; i<pattern.length(); i++)
    {
        basemod1=(basemod1*MAX+pattern[i])%MOD1;
        basemod2=(basemod2*MAX+pattern[i])%MOD2;
        if(i)
        {
            base1=(base1*MAX)%MOD1;
            base2=(base2*MAX)%MOD2;
        }
    }
    long long mod1=0,mod2=0;

    for(int i=0; i<pattern.length(); i++)
    {
        char here=text[i];
        mod1=(mod1*MAX+here)%MOD1;
        mod2=(mod2*MAX+here)%MOD2;
    }
    if(basemod1==mod1 && basemod2==mod2)
    {
        results.push_back(0);
    }
    char last=text[0];

    for(int i=1; i<text.length()-pattern.length()+1; i++)
    {
        long long delete1=(base1*last)%MOD1;
        long long delete2=(base2*last)%MOD2;

        mod1=(((mod1-delete1+MOD1)*MAX)%MOD1+text[i+pattern.length()-1])%MOD1;
        mod2=(((mod2-delete2+MOD2)*MAX)%MOD2+text[i+pattern.length()-1])%MOD2;

        if(mod1==basemod1 && mod2==basemod2)
        {
            results.push_back(i);
        }
        last=text[i];
    }

    out<<results.size()<<endl;
    int ending=results.size();
    ending=min(ending,1000);
    for(int i=0; i<ending; i++)
    {
        out<<results[i]<<" ";
    }


}



int main()
{
    read();
    if(pattern.length()>text.length())
        out<<0;
    else
        rabin_karp();
}