Cod sursa(job #3160388)

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

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

string pattern,str;

#define BASE1 256
#define BASE2 256
#define MOD1 666013
#define MOD2 1000007
long long hash1,hash2;
long long power1,power2;

long long lgput(long long x,long long p,long long 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);
}

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

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

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

long long main(){
    in>>pattern>>str;
    if(pattern.length()>str.length()){
        out<<0;
        return 0;
    }

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

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

    for(long long 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 <long long>v;

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

    for(long long 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(long long i=0;i<v.size();i++){
        out<<v[i]<<" ";
    }
}