Chaînes de caractères

• Recherche de motifs (Knuth-Morris-Pratt, Rabin-Karp)
• Arbre lexicographique
• Plus grande période
• Plus long palindrome (Manacher)
• Facteur commun maximal

Programmation dynamique

• Plus court chemin dans un DAG
• Plus longue sous-séquence commune
• Distance d’édition de Levenshtein
• Plus longue sous-séquence commune
• Plus longue sous-séquence croissante
• Stratégie gagnante dans un jeu à deux joueurs
• Multiplication d’une séquence de matrices

Tableaux

• Fusion de listes triées
• Fenêtre avec k éléments distincts
• Somme d’un intervalle
• Doublon d’un intervalle
• Plus grande somme d’un intervalle
• Requêtes de minimum sur un intervalle
• Requêtes de somme sur un intervalle

Intervalles

• Arbre d’intervalles
• Union d’intervalles
• Couverture d’intervalles

Graphes

• DFS : Parcours en profondeur
• BFS : Parcours en largeur
• Composantes connexes
• Composantes biconnexes
• Tri topologique
• 2-SAT
• Composantes fortement connexes

Cycles

• Chemin eulérien
• Problème du postier chinois (Google Hash Code 2014)
• Cycles de ratio poids sur longueur minimal (Karp)
• Cycles de ratio coût sur temps minimal

Plus courts chemins

• Graphes avec poids 0 ou 1
• Graphes avec poids positifs ou nuls (Dijkstra)
• Graphes avec poids arbitraires (Bellman-Ford)
• Toutes paires source-destination
• Grille

Couplages et flots

• Couplage maximum biparti
• Couplage parfait de poids maximal (hongrois, Kuhn-Munkres)
• Couplage planaire sans croisement
• Mariage stable (Gale-Shapley)
• Flot maximal (Ford-Fulkerson, Edmonds-Karp)
• Coupe minimale
• Coupe minimale pour graphe planaire
• Largeur d’un ordre partiel

Arbres

• Arbre couvrant de poids minimal
• Requêtes d’ancêtre commun le plus proche
• Plus long chemin dans un arbre

Ensembles

• Sac à dos
• Rendu de monnaie
• SUBSET-SUM
• k-somme

Points et polygones

• Enveloppe convexe
• Paire de points les plus proches
• Polygone rectilinéaire simple

Rectangles

• Plus grand carré dans une grille
• Plus grand rectangle dans un histogramme
• Plus grand rectangle dans une grille
• Union de rectangles
• Union de rectangles disjoints

Calculs

• PGCD
• Bézout
• Coefficients binomiaux
• Exponentiation rapide
• Nombres premiers
• Évaluation d’une expression arithmétique
• Systèmes d’équations linéaires

Exploration exhaustive

• Sudoku
• Énumération de permutations
• Le compte est bon