I den längsta gemensamma substring (LCS) problem, vi ges två strängar S och T, var och en av längd som mest n, och vi uppmanas att hitta en längsta sträng som förekommer som ett fragment av både S och T. Detta är ett klassiskt och välstuderat problem i datavetenskap med en känd O (n)-tid lösning. I den helt dynamiska versionen av problemet, redigera åtgärder är tillåtna i någon av de två strängar, och vi uppmanas att rapportera en LCS efter varje sådan operation. Vi presenterar den första lösningen på detta problem som kräver sublinjär tid per redigeringsoperation. I synnerhet visar vi hur man returnerar en LCS i Õ(n 2/3 ) 1 gång (eller Õ ( ș n) tid om redigeringar är tillåtna i endast en av de två strängar) efter varje operation med Õ(n) utrymme. Denna forskningslinje initierades nyligen av författarna [SPIRE 2017] i en något begränsad dynamisk variant. En datastruktur i storlek Õ(n) som returnerar en LCS av de två strängarna efter en enda redigering (som återställs efteråt) i Õ(1) tid presenterades. Vid CPM 2018 studerade tre artiklar analogt begränsade dynamiska varianter av problem på strängar. Vi visar att våra tekniker kan användas för att erhålla fullt dynamiska algoritmer för flera klassiska problem på strängar, nämligen att beräkna den längsta upprepningen, den längsta palindromen och den längsta Lyndon substrängen av en sträng. De enda tidigare kända sublinjära tid dynamiska algoritmer för problem på strängar erhölls för att upprätthålla en dynamisk samling strängar för jämförelsefrågor och för mönstermatchning med de senaste framsteg som gjorts av Gawrychowski et al. [SODA 2018] och av Clifford et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). Som ett mellanproblem överväger vi att beräkna det önskade resultatet på en sträng med en given uppsättning k-redigeringar, vilket leder oss, i synnerhet, till att svara på interna frågor på en sträng. Inmatningen till en sådan fråga anges av en delsträng (eller delsträngar) av en given sträng. Datastrukturer för att besvara interna frågor som föreslogs av Kociumaka et al. [SODA 2015] och av Gagie et al. [CCCG 2013] används, tillsammans med nya datastrukturer för flera typer av frågor som vi utvecklar - dessa frågor inkluderar att beräkna en LCS på flera understrängar. Men eftersom det är troligt att de mest allmänna interna LCS-frågorna inte kan besvaras effektivt, utformar vi också ett annat system som kräver en tillämpning av skillnaden täcker. Andra ingredienser i våra algoritmer inkluderar suffixträdet, heavy-path nedbrytningar, ortogonala intervall frågor, och sträng periodicitet.
Därefter, Amir et al. REF ansågs vara en helt dynamisk version av problemet, där redigeringsåtgärderna tillämpas sekventiellt.
Longest Common Substring Made Fully Dynamic
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}