I detta papper undersöker vi strängblocksredigeringsavstånd, där två strängar A och B jämförs genom att extrahera samlingar av understrängar och placera dem i korrespondens. Denna modell står för vissa fenomen som förekommer i viktiga tillämpningar i verkligheten, inklusive penndatorer och molekylärbiologi. Det grundläggande problemet medger en familj av variationer beroende på om strängarna måste matchas i sin helhet, och om överlappning är tillåten. Vi visar att flera varianter är NPfullständiga, och ger polynom-tid algoritmer för att lösa resten.
Lopresti och Tompkins REF jämför två strängar genom att extrahera samlingar av understrängar och placera dem i motsvarande ordning.
Block edit models for approximate string matching
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}