Cod sursa(job #3160090)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 22 octombrie 2023 21:29:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in  ("strmatch.in");
ofstream out("strmatch.out");

string pattern,str;

#define BASE1 100
#define BASE2 27
#define MOD1 666013
#define MOD2 7328773
int hash1,hash2;
int power1,power2;

int lgput(int x,int p,int mod){
    if(p==1){
        return x;
    }
    if(p%2==1){
        return x*lgput(x*x%mod,p/2,mod)%mod;
    }
    return lgput(x*x%mod,p/2,mod);
}

int compute(string s,int base,int mod){
    int hash=0;
    for(int i=0;i<s.length();i++){
        hash=(hash*base+s[i])%mod;
    }
    return hash;
}

int add(int hash,char ch,int base,int mod){
    return (hash*base+ch)%mod;
}

int remove(int hash,int base,int mod,int power,char ch){
    hash-=(ch*power)%mod;
    if(hash<0){
        hash+=mod;
    }
    return hash;
}

int main(){
    in>>pattern>>str;

    power1=lgput(BASE1,pattern.length()-1,MOD1);
    power2=lgput(BASE2,pattern.length()-1,MOD2);

    int strhash1=0,strhash2=0;
    int patternhash1=0,patternhash2=0;
    int nr=0;

    for(int i=0;i<pattern.length();i++){
        strhash1=add(strhash1,str[i],BASE1,MOD1);
        strhash2=add(strhash2,str[i],BASE2,MOD2);
        
        patternhash1=add(patternhash1,pattern[i],BASE1,MOD1);
        patternhash2=add(patternhash2,pattern[i],BASE2,MOD2);
    }

    vector <int>v;

    if(strhash1==patternhash1 && strhash2==patternhash2){
        nr++;
        v.push_back(0);
    }

    for(int i=1;i<=str.length()-pattern.length();i++){
        strhash1=remove(strhash1,BASE1,MOD1,power1,str[i-1]);
        strhash2=remove(strhash2,BASE2,MOD2,power2,str[i-1]);

        strhash1=add(strhash1,str[i+pattern.length()-1],BASE1,MOD1);
        strhash2=add(strhash2,str[i+pattern.length()-1],BASE2,MOD2);

        if(strhash1==patternhash1 && strhash2==patternhash2){
            nr++;
            if(nr<=1000){
                v.push_back(i);
            }
        }
    }

    out<<nr<<'\n';
    for(int i=0;i<v.size();i++){
        out<<v[i]<<" ";
    }
}