Cod sursa(job #2433804)

Utilizator mihai2003LLL LLL mihai2003 Data 29 iunie 2019 10:54:04
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>

class str_search{
    std::string pattern,text;
    std::vector<int>pos;
    const static int d=256;
    const static int MOD=881269;
public:
    str_search(){}
    str_search(std::string a,std::string b):pattern(a),text(b){}
    void search(std::ofstream& out){
        int th=0,ph=0,h=1;
        for(int i=0;i<pattern.size()-1;i++)
            h=(h*d)%MOD;
        for(int i=0;i<pattern.size();i++)
            th=(d*th+text[i])%MOD,ph=(d*ph+pattern[i])%MOD;
        for(int i=0;i<=text.size()-pattern.size()+1;i++){
            if(th==ph){
                bool ok=1;
                for(int j=0;j<pattern.size();j++)
                    if(pattern[j]!=text[i+j]){
                        ok=0;
                        break;
                    }
                if(ok)
                    pos.push_back(i);
            }
            th=(d*(th-text[i]*h)+text[i+pattern.size()])%MOD;
            if(th<0)
                th+=MOD;
        }
        out<<pos.size()<<'\n';
        for(int i=0;i<pos.size();i++)
            out<<pos[i]<<" ";
    }

};

std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::string pat,txt;
int main(){
    in>>pat>>std::ws>>txt;
    str_search(pat,txt).search(out);
    return 0;
}