ForHosting KIT · Texte et IA

Calculateur LCS

Trouvez la plus longue suite de caractères que deux chaînes partagent dans le même ordre, même avec des trous : ABCBDAB et BDCABA en partagent 4, par exemple BCBA. Vous obtenez la longueur et une sous-séquence valide, vérifiable à l'œil. Gratuit dans votre navigateur.

Gratuit
Fonctionne dans votre navigateur
Sans inscription
Vos données restent sur votre appareil

Lancer gratuitement Voir l’API

Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Exemple résolu

Si vous saisissez

Chaîne A: ABCBDAB
Chaîne B: BDCABA

Vous obtenez

Len a: 7
Len b: 6
Longueur: 4
Sous-séquence: BCBA

Le problème de la plus longue sous-séquence commune demande la plus longue suite de caractères qui apparaît dans le même ordre dans deux chaînes d'entrée, sans exiger la contiguïté. C'est le fondement en programmation dynamique des outils de diff ligne par ligne, des aides de fusion en contrôle de version, des détecteurs de plagiat qui tolèrent un réordonnancement bruyant, et de la comparaison de séquences biologiques lorsque les insertions et suppressions comptent plus qu'une sous-chaîne exacte. Ce calculateur de plus longue sous-séquence commune accepte deux chaînes, remplit une table de longueurs classique en temps linéaire par rapport au produit des longueurs, reconstruit un LCS valide par rétroparcours et renvoie à la fois la longueur numérique et la chaîne de sous-séquence. Les entrées vides sont valides et donnent une longueur nulle.

Ce qu'est (et n'est pas) une plus longue sous-séquence commune

Une sous-séquence d'une chaîne est toute chaîne obtenue en supprimant zéro ou plusieurs caractères sans réordonner les survivants. Une sous-séquence commune de deux chaînes est une chaîne qui est sous-séquence des deux. Une plus longue sous-séquence commune, ou LCS, est toute sous-séquence commune dont la longueur est maximale parmi toutes les sous-séquences communes.

Contrairement à une plus longue sous-chaîne commune, un LCS n'a pas besoin d'occuper un bloc contigu dans l'une ou l'autre entrée : le couple classique ABCBDAB et BDCABA admet plusieurs chaînes LCS de longueur quatre, comme BCBA et BDAB, selon les égalités choisies par la reconstruction. Les algorithmes de diff et les outils d'alignement d'ADN s'appuient sur cette notion non contiguë parce que les vraies éditions insèrent et suppriment des symboles au lieu de seulement faire glisser une fenêtre fixe.

La longueur d'un LCS est un score de similarité utile ; les caractères reconstruits servent lorsque vous voulez un squelette d'alignement explicite à côté du score. Il ne renvoie pas tous les LCS possibles, scripts d'édition ni pourcentages de similarité—ce sont des problèmes distincts bâtis sur la même idée de table DP.

Quand la sous-séquence commune est utile

Les cours d'informatique et les juges en ligne ont besoin d'un oracle de référence qui renvoie une longueur correcte et une sous-séquence valide pour de courtes chaînes arbitraires sans que les étudiants collent des solutions dans un IDE complet. Les fonctions produit proches du diff—résumés de changements, indices de conflit de fusion, alignement de lignes de journal—veulent souvent la longueur LCS comme signal de similarité peu coûteux avant un passage plus lourd de distance d'édition.

Les démos pédagogiques de bioinformatique utilisent des chaînes de l'alphabet ADN jouet (A, C, G, T) pour montrer comment insertions et suppressions laissent encore un long squelette partagé. Gardez les chaînes sous le plafond de longueur, figez la sous-séquence reconstruite dans les tests si l'instance parmi plusieurs réponses aussi longues vous importe, et vous obtenez des résultats LCS reproductibles sans monter votre propre bibliothèque numérique.

Cas d’usage

Devoirs d'algorithmes et démos de cours

Donnez aux étudiants deux chaînes courtes et vérifiez à la fois la longueur LCS et que la sous-séquence renvoyée apparaît vraiment dans l'ordre dans chaque entrée.

Notation automatique LMS et concours

Notez les devoirs de DP avec un oracle déterministe qui rejette les entrées invalides et n'invente jamais une sous-séquence plus longue que la table classique ne le permet.

Pré-contrôles de diff et similarité de séquences

Notez la structure ordonnée partagée entre deux textes ou chaînes ADN jouet avant un pipeline plus lourd de distance d'édition ou d'alignement.

Questions fréquentes

Le LCS est-il la même chose que la plus longue sous-chaîne commune ?

Non. Une sous-chaîne doit être contiguë ; une sous-séquence peut sauter des caractères. Ce calculateur résout le problème de sous-séquence par programmation dynamique classique.

Quelles sont les limites de longueur et les règles pour les chaînes vides ?

Chaque chaîne peut comporter au plus 500 caractères. Les chaînes vides sont autorisées et produisent length 0 avec une sous-séquence vide.

Pourquoi deux chaînes peuvent-elles avoir plusieurs plus longues sous-séquences communes ?

Parce que les égalités sont fréquentes. ABCBDAB et BDCABA en partagent plusieurs de longueur 4, comme BCBA et BDAB. Le calculateur en renvoie une et tranche toujours de la même façon, donc une même paire donne toujours la même réponse.

À quoi sert la longueur de la LCS ?

Elle sert de mesure de ressemblance peu coûteuse. Résumés de modifications, aides à la fusion et alignement de journaux peuvent l'utiliser avant un calcul de distance plus lourd, et les démonstrations avec des lettres d'ADN montrent comment un long tronc commun résiste.

Comment vérifier que la sous-séquence renvoyée est correcte ?

Vérifiez que ses caractères apparaissent dans le même ordre dans les deux chaînes, en sautant les autres, et que sa longueur correspond au nombre indiqué. BCBA passe dans ABCBDAB et dans BDCABA : c'est ainsi que l'on corrige les réponses.

Outils associés

Pour les développeurs — accès API

Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.

Endpoint

POSThttps://api.kit.forhosting.com/dev/longest-common-subsequence

Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.

Appeler depuis votre stack

curl -X POST https://api.kit.forhosting.com/dev/longest-common-subsequence \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"string_a":"ABCBDAB","string_b":"BDCABA"}'

const res = await fetch("https://api.kit.forhosting.com/dev/longest-common-subsequence", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "string_a": "ABCBDAB",
    "string_b": "BDCABA"
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/longest-common-subsequence",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "string_a": "ABCBDAB",
    "string_b": "BDCABA"
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/longest-common-subsequence", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"string_a":"ABCBDAB","string_b":"BDCABA"}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"string_a":"ABCBDAB","string_b":"BDCABA"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/longest-common-subsequence", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

Exemple de requête

{
  "string_a": "ABCBDAB",
  "string_b": "BDCABA"
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.longest_common_subsequence",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.

Tarifs

par requête$0.002

Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.

Erreurs

HTTP	Code	Signification
`401`	`unauthorized`	Clé API absente ou invalide : vérifiez l’en-tête Authorization.
`402`	`insufficient_balance`	Solde insuffisant : rechargez votre compte pour lancer cette tâche.
`404`	`unknown_type`	Type de tâche inconnu : vérifiez le champ type de votre requête.
`429`	`rate_limited`	Trop de requêtes : ralentissez la cadence, puis réessayez.

Notes techniques

Contrat d'entrée, algorithme, forme de la réponse et limites

La complexité est O(m·n) en temps et O(m·n) en mémoire dans la forme naïve de table utilisée ici—adaptée au plafond de longueur, volontairement simple pour l'enseignement et des goldens déterministes. Envoyez en POST un corps JSON avec deux champs chaîne obligatoires : string_a et string_b (les alias a, s1, first, text_a et b, s2, second, text_b sont acceptés). Les deux peuvent être vides ; les deux doivent être de vraies chaînes JSON, pas des nombres ni des tableaux. Les champs manquants, les types non chaîne et les entrées trop longues échouent avec invalid_input et ne sont pas facturés. En cas de succès le corps renvoie string_a et string_b, indique len_a et len_b, et inclut length (la longueur LCS) plus subsequence (une chaîne LCS, éventuellement vide). En interne le solveur alloue une table d'entiers (m+1) par (n+1), pose dp[i][j] à dp[i-1][j-1]+1 lorsque les préfixes coïncident sur le dernier caractère, sinon le max des cellules du haut et de gauche, puis parcourt depuis le coin bas-droit : une paire concordante ajoute ce caractère et avance en diagonale ; en cas d'égalité il préfère monter (abandonner string_a) pour que l'instance reconstruite soit stable entre runtimes.

Où une API LCS apporte une vraie valeur

Les correcteurs automatiques LMS peuvent appeler l'API avec des paires fixes et affirmer à la fois la longueur et que la sous-séquence renvoyée est une sous-séquence de chaque entrée, capturant des bugs de table d'un qui ne échouent que sur des cas vides ou d'un seul caractère. Comme l'implémentation est pure parse de niveau A, chaque appel réussi coûte le prix de base publié $0.002 sans jetons de modèle ni réseau sortant.

Questions techniques

Comment calculer la plus longue sous-séquence commune de deux chaînes ?

Envoyez string_a et string_b comme chaînes JSON. L'API renvoie length (longueur LCS) et subsequence (une sous-séquence commune maximale), plus les entrées renvoyées et leurs longueurs.

Quel LCS est renvoyé lorsqu'il en existe plusieurs ?

Tout LCS de longueur maximale est correct. Cette implémentation utilise un rétroparcours fixe (préférer abandonner string_a en cas d'égalité) pour que les mêmes entrées donnent toujours la même chaîne de sous-séquence.

Combien coûte le calculateur de plus longue sous-séquence commune ?

L'outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; l'entrée invalide n'est pas facturée.

Consulter la documentation complète du KIT →

Lancer gratuitement