src/misc/boyermoore.hpp

View this file on GitHub
Last update: 2025-12-30 15:03:15+09:00
Include: #include "src/misc/boyermoore.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

vector<int> boyer_moore_generalized(vector<int> a,int k){
    vector<int> val(k,0),cnt(k,0);

    for_each(all(a),[&](int& x) {
        rep(i,k){
            if(cnt[i]&&val[i]==x){
                cnt[i]++;
                return;
            }
        }
        rep(i,k){
            if(!cnt[i]){
                val[i]=x;
                cnt[i]=1;
                return;
            }
        }
        rep(i,k) cnt[i]--;
    });
    vector<int> ret;
    rep(i,k) if(cnt[i]>0){
        int s=0;
        for(int x: a)
            if(val[i]==x) s++;
        if(s>si(a)/(k+1)) ret.push_back(val[i]);
    }
    sort(all(ret));
    ret.erase(unique(all(ret)),ret.end());
    return ret;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/misc/boyermoore.hpp"

vector<int> boyer_moore_generalized(vector<int> a,int k){
    vector<int> val(k,0),cnt(k,0);

    for_each(all(a),[&](int& x) {
        rep(i,k){
            if(cnt[i]&&val[i]==x){
                cnt[i]++;
                return;
            }
        }
        rep(i,k){
            if(!cnt[i]){
                val[i]=x;
                cnt[i]=1;
                return;
            }
        }
        rep(i,k) cnt[i]--;
    });
    vector<int> ret;
    rep(i,k) if(cnt[i]>0){
        int s=0;
        for(int x: a)
            if(val[i]==x) s++;
        if(s>si(a)/(k+1)) ret.push_back(val[i]);
    }
    sort(all(ret));
    ret.erase(unique(all(ret)),ret.end());
    return ret;
}