Vi presenterar randomiserade algoritmer för att lösa följande strängmatchningsproblem och några av dess generaliseringar: Med tanke på en sträng X av längd n (mönstret) och en sträng Y (texten), hitta den första förekomsten av X som ett på varandra följande block inom Y. Algoritmerna representerar strängar av längd n av mycket kortare strängar som kallas fingeravtryck, och uppnå deras effektivitet genom att manipulera fingeravtryck istället för längre strängar. Algoritmerna kräver ett konstant antal lagringsplatser, och körs i huvudsak i realtid. De är konceptuellt enkla och enkla att genomföra. Metoden generaliserar lätt till högre-dimensionella mönstermatchning problem. Textbehandlingssystem måste göra det möjligt för användarna att söka efter en viss teckensträng i en textsamling. Databassystemen måste kunna söka efter poster med angivna värden i angivna fält. Sådana problem är fall av följande strängmatchning problem: För en specificerad uppsättning ((X(i), Y(i)) par strängar, bestämma, om möjligt, en r sådan att X(r) = Y(r). Vanligtvis anges uppsättningen inte genom explicit uppräkning av paren, utan snarare genom en regel för att beräkna paren (X(i), Y(i) från vissa givna data. Vi presenterar en randomiserad algoritm för att lösa det här problemet. Algoritmen associerar med varje sträng X ett fingeravtryck I#@' ) som är mycket kortare än strängen själv. Sökandet efter en matchning jämför sedan korta fingeravtryck istället för långa strängar. Algoritmen väljer jngerprint-funktionen och slumpmässigt från en familj av enkla funktioner. Oavsett vilken inmatning ((X(i), Y(i))) som presenteras är det osannolikt att algoritmen ger en falsk matchning, där två fingeravtryck är överens även om de ursprungliga strängarna inte gör det. Det mest studerade mönstermatchning problemet är följande: Med tanke på ett mönster X av längd n och en text Y av längd m 2 n, hitta den första förekomsten av X som en på varandra följande delsträng av Y. Flera linjära tidsalgoritmer har getts för detta problem. har hittat en realtidsalgoritm med hjälp av ett konstant antal register. Vår metod, baserad på fingeravtrycksfunktioner, löper i huvudsak i realtid; den exakta innebörden av detta uttalande anges i Theorem 4. Den kräver ett konstant antal register och behöver en delsträng av textens längd n i huvudminnet. En version, beskriven av Algoritm 3, körs strikt i realtid men tillåter en bevisligen mindre sannolikhet för fel. producera samma teoretiska tidsgränser som deterministiska algoritmer och kräver en konkurrenskraftig eller en betydande fördel av våra algoritmer är att de
En av de första algoritmerna var Karp-Rabin algoritm REF som användes för strängmatchning problem och det är baserat på modulär aritmetik för hashing.
Efficient randomized pattern-matching algorithms
{'venue': 'IBM J. Res. Dev.', 'journal': 'IBM J. Res. Dev.', 'mag_field_of_study': ['Computer Science']}