Space efficient LCS using Hirschberg's algorithm
I maintainer di solito rispondono entro 1 giorno
@ggyuchive ci sta già lavorando.
Dal 7/1/2026.
Valutazione
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Idoneità per principianti
- 42/100
- Tipo di issue
- Refactoring
- Chiarezza
- Abbastanza chiara
- Stato di attività
- Ferma
- Stack tecnologico
- cpp
- Ambito
- database, performance
Direzione di ricerca
Inizia individuando l'implementazione del comando LCS di kvrocks e i relativi test esistenti, quindi leggi come l'approccio attuale di programmazione dinamica calcola e recupera il risultato. Il lavoro è completato quando LCS utilizza l'algoritmo di Hirschberg, mantiene il recupero della stringa LCS, riduce lo spazio a O(|S|+|T|) e i test pertinenti hanno esito positivo.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Search before asking
- I had searched in the issues and found no similar issues.
Motivation
In kvrocks LCS command, it uses Dynamic Programming. When two string S, T and get LCS(S, T),
- Time Complexity: O(|S||T|)
- Space Complexity: O(|S||T|)
When |S| and |T| is about 10000, it requires over 400MB.
Solution
We can reduce space complexity to O(|S|+|T|) using Hirschberg's algorithm, also it can recover LCS string.
Relevant paper: A Linear Space Algorithm for Computing Maximal Common Subsequences (Author: D.S. Hirschberg)
Are you willing to submit a PR?
- I'm willing to submit a PR!
- Lingua principale
- C++
- Stelle
- 4.5k
- Fork
- 686
- Merge medio
- 2g 13h
- PR unite (30g)
- 40
Preparare l'ambiente
Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.
- Include un Dockerfile o un file Docker Compose
- Nessun modello di pull request
- Nessuna guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di apache/kvrocks
-
HSETEXPIRE with an overflowing TTL returns OK and deletes the whole hashForse già presa @anubhavgupta121 l’ha presa 17 giorni fa. Apertabug
Difficoltà 2/5 1-3 ore Idoneità per principianti 74/100
I maintainer di solito rispondono entro 1 giorno
-
`GEOSEARCH` / `GEORADIUS` with a negative radius hangsForse già presa @ggyuchive l’ha presa 6 giorni fa. Apertabug
Difficoltà 3/5 1-2 giorni Idoneità per principianti 25/100
I maintainer di solito rispondono entro 1 giorno
-
`ZDIFFSTORE` and `ZINTERSTORE` with numkeys 0 crash the server (SIGSEGV)Forse già presa @siddiqueirshad l’ha presa 8 giorni fa. Apertabug
Difficoltà 2/5 1-3 ore Idoneità per principianti 35/100
I maintainer di solito rispondono entro 1 giorno
-
Support the `SUNIONCARD` commandForse già presa @PoisonGodv l’ha presa 2 giorni fa. Apertaenhancement
Difficoltà 3/5 1-2 giorni Idoneità per principianti 58/100
apache/kvrocks#3723 · 1 commento ·
I maintainer di solito rispondono entro 1 giorno
-
`NAMESPACE ADD/SET/DEL` and `CONFIG REWRITE` rewrite `kvrocks.conf` without fsync: after a power loss new namespaces vanish, and deleted namespaces / rotated tokens are valid againForse già presa @Tyagiquamar l’ha presa 13 giorni fa. Apertabug
Difficoltà 4/5 3-5 giorni Idoneità per principianti 50/100
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di apache/kvrocks
Issue simili
-
Difficoltà 1/5 1-3 ore Idoneità per principianti 68/100
eic/TimeframeBuilder#102 ·
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
AcademySoftwareFoundation/OpenImageIO#5662 ·
I maintainer di solito rispondono entro 2 giorni
-
python
Difficoltà 2/5 1-3 ore Idoneità per principianti 67/100
OpenChemistry/avogadrolibs#3295 · 2 commenti ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 65/100
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
Tracktion/tracktion_engine#482 ·
I maintainer di solito rispondono entro 1 giorno