#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "grader.h"
#include "lang.h"
#define int long long
using namespace std;
const int langs=56,buckets=1<<20,max_ngrams=4;
const float smooth=0.08,prior=1.0;
struct naivebayes{
unsigned short cnt[langs][buckets][2];
signed total[langs][2];
void train(signed *E, int L){
for(int i = 0; i+max_ngrams <= 100; i++){
int h=0;
for(int j = 0; j < max_ngrams-1; j++){
h=(h*263+E[i+j])%buckets;
}
cnt[L][h][0]++;
h=(h*263+E[i+max_ngrams-1])%buckets;
cnt[L][h][1]++;
total[L][0]++;
total[L][1]++;
}
}
signed predict(signed *E){
float best=-1e300;
int blang=0,sum=0;
for(int i = 0; i < langs; i++)sum+=total[i][0]+total[i][1];
for(int L = 0; L < langs; L++){
float prob=log((total[L][0]+total[L][1]+prior)/(sum+prior*langs));
for(int i = 0; i+max_ngrams <= 100; i++){
int h=0;
for(int j = 0; j < max_ngrams-1; j++){
h=(h*263+E[i+j])&(buckets-1);
}
prob+=log((cnt[L][h][0]+smooth)/(total[L][0]+smooth*buckets));
h=(h*263+E[i+max_ngrams-1])%buckets;
prob+=log((cnt[L][h][1]+smooth)/(total[L][1]+smooth*buckets));
}
if(prob>=best){
best=prob;
blang=L;
}
}
return blang;
}
}NB;
void excerpt(signed *E){
int qu=language(NB.predict(E));
NB.train(E,qu);
}
