Substringsökning

Substringsökning är problemet att hitta förekomster av en viss mönstersträng P inom en större text T. I den enkla versionen söker man efter alla positioner i T där T[i..i+m-1] = P, där n är längden på T och m längden på P. Det finns också varianter där flera mönster ska hittas i samma text, vilket används i sammanhang som filtrering, sökmotorer och bioinformatik.

Den naïva metoden jämför mönstret med varje delsträng i texten och har tidskomplexiteten O(nm). Mångsidiga algoritmer har utvecklats för effektiv substringsökning. Knuth–Morris–Pratt (KMP) använder en prefixfunktion för mönstret och kan hitta alla matchningar i O(n+m) utan att backspola i texten. Rabin–Karp bygger på hashing av delsträngar och mönstret P, vilket ger förväntad O(n+m) tid vid bra hashfunktioner. Boyer–Moore arbetar med skenande text och bakåtsökning och är ofta mycket snabbt i praktiken, men worst-case kan vara O(nm). För flera mönster används Aho–Corasick-trädet/automaton, som kan hitta alla förekomster av en uppsättning mönster i tiden O(n + z), där z är antalet matchningar.

Moderna tillvägagångssätt använder även suffixstrukturer som suffixträd och suffixautomaton för underfrågor om substrings, liksom reguljära uttryck och tillåtna avvikelser. Användningar inkluderar textsökning i dokument, textredigerare och grep-liknande verktyg, bioinformatik för DNA- och proteinsekvenser, innehållsfiltrering och nätverksskydd.