Liste Simplement Chaînée

Cette implémentation utilise des tableaux statiques pour simuler une liste chaînée, ce qui est particulièrement efficace en programmation compétitive pour éviter les allocations dynamiques coûteuses.

// tete : indice du premier élément
// val[] : stocke les données
// suivant[] : pointeur vers l'indice suivant
// curseur : prochain emplacement disponible
int tete, val[N], suivant[N], curseur;

void initialiser() {
    tete = -1;
    curseur = 0;
}

void ajouter_en_tete(int x) {
    val[curseur] = x;
    suivant[curseur] = tete;
    tete = curseur++;
}

void inserer_apres(int k, int x) {
    val[curseur] = x;
    suivant[curseur] = suivant[k];
    suivant[k] = curseur++;
}

void supprimer_apres(int k) {
    suivant[k] = suivant[suivant[k]];
}

Liste Doublement Chaînée

Ici, nous gérons deux liens par nœud pour permettre des déplacements dans les deux sens.

int contenu[N], prec[N], succ[N], id;

void init_double() {
    // 0 est la sentinelle gauche, 1 est la sentinelle droite
    succ[0] = 1;
    prec[1] = 0;
    id = 2;
}

void inserer_a_droite(int k, int x) {
    contenu[id] = x;
    prec[id] = k;
    succ[id] = succ[k];
    prec[succ[k]] = id;
    succ[k] = id++;
}

void retirer_noeud(int k) {
    succ[prec[k]] = succ[k];
    prec[succ[k]] = prec[k];
}

Pile Monotnoe

La pile monotone permet de trouver efficacement le premier élément plus petit (ou plus grand) à gauche d'une position donnée.

int pile[N], sommet = 0;

void resoudre_pile_monotone(int n) {
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        while (sommet > 0 && pile[sommet] >= x) sommet--;
        
        if (sommet == 0) printf("-1 ");
        else printf("%d ", pile[sommet]);
        
        pile[++sommet] = x;
    }
}

Fenêtre Glissante (File Monotone)

Utile pour obtenir le minimum ou le maximum dans chaque fenêtre de taille k d'un tableau.

int q[N], a[N];

void fenetre_glissante(int n, int k) {
    int avant = 0, arriere = -1;
    for (int i = 0; i < n; i++) {
        // Retirer les éléments hors de la fenêtre
        if (avant <= arriere && i - k + 1 > q[avant]) avant++;
        
        // Maintenir la monotonie
        while (avant <= arriere && a[q[arriere]] >= a[i]) arriere--;
        q[++arriere] = i;
        
        if (i >= k - 1) printf("%d ", a[q[avant]]);
    }
}

Algorithme KMP (Knuth-Morris-Pratt)

Recherche de motifs optimisée utilisant un tableau de préfixes.

int pi[N]; // Tableau de repli
char motif[N], texte[M];

void kmp_search(int n, int m) {
    // Construction du tableau de préfixes
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && motif[i] != motif[j + 1]) j = pi[j];
        if (motif[i] == motif[j + 1]) j++;
        pi[i] = j;
    }

    // Phase de recherche
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && texte[i] != motif[j + 1]) j = pi[j];
        if (texte[i] == motif[j + 1]) j++;
        if (j == n) {
            printf("Occurence à : %d\n", i - n);
            j = pi[j];
        }
    }
}

Structure Trie (Arbre de Préfixes)

Stockage et recherche rapide de chaînes de caractères.

int arbre[N][26], marqueur[N], index_noeud;

void ajouter_mot(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!arbre[p][c]) arbre[p][c] = ++index_noeud;
        p = arbre[p][c];
    }
    marqueur[p]++;
}

int compter_mot(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!arbre[p][c]) return 0;
        p = arbre[p][c];
    }
    return marqueur[p];
}

Union-Find (DSU)

Gestion d'ensembles disjoints avec compression de chemin.

int parent[N], distance_racine[N];

int chercher(int x) {
    if (parent[x] != x) {
        int racine = chercher(parent[x]);
        distance_racine[x] += distance_racine[parent[x]];
        parent[x] = racine;
    }
    return parent[x];
}

void unir(int a, int b) {
    int racine_a = chercher(a), racine_b = chercher(b);
    if (racine_a != racine_b) {
        parent[racine_a] = racine_b;
    }
}

Tas Binaire (Min-Heap)

Implémentation d'une file de priorité manuelle.

int tas[N], taille_tas;

void descendre(int u) {
    int petit = u;
    if (u * 2 <= taille_tas && tas[u * 2] < tas[petit]) petit = u * 2;
    if (u * 2 + 1 <= taille_tas && tas[u * 2 + 1] < tas[petit]) petit = u * 2 + 1;
    if (petit != u) {
        swap(tas[u], tas[petit]);
        descendre(petit);
    }
}

void monter(int u) {
    while (u / 2 && tas[u / 2] > tas[u]) {
        swap(tas[u / 2], tas[u]);
        u /= 2;
    }
}

void construire_tas(int n) {
    taille_tas = n;
    for (int i = n / 2; i >= 1; i--) descendre(i);
}

Hachage (Hash Table)

Méthode de l'adressage ouvert

const int M_HASH = 200003, VIDE = 0x3f3f3f3f;
int table[M_HASH];

int localiser(int x) {
    int k = (x % M_HASH + M_HASH) % M_HASH;
    while (table[k] != VIDE && table[k] != x) {
        k++;
        if (k == M_HASH) k = 0;
    }
    return k;
}

Méthode par chaînage

int h_tete[N], e_val[N], e_suiv[N], e_idx;

void insertion_hash(int x) {
    int k = (x % N + N) % N;
    e_val[e_idx] = x;
    e_suiv[e_idx] = h_tete[k];
    h_tete[k] = e_idx++;
}

Hachage de Chaînes (Rolling Hash)

Calculer une empreinte numérique pour comparer des sous-chaînes en O(1).

typedef unsigned long long ull;
const int BASE = 131;
ull h_pref[N], puiss[N];

ull calculer_hash(int l, int r) {
    return h_pref[r] - h_pref[l - 1] * puiss[r - l + 1];
}

void precalculer(char *s, int n) {
    puiss[0] = 1;
    for (int i = 1; i <= n; i++) {
        h_pref[i] = h_pref[i - 1] * BASE + s[i];
        puiss[i] = puiss[i - 1] * BASE;
    }
}