Substringen

Substringen zijn alle mogelijke opeenvolgende delen van een tekenreeks (string). Een substring bestaat uit een aaneengesloten reeks tekens uit de oorspronkelijke string. De lege string wordt in veel definities ook als substring gerekend. Substrings hebben lengte variërend van 0 tot de lengte van de string.

Voor de string 'abcdef' zijn substrings zoals 'a', 'ab', 'abc', 'b', 'bc', 'cde', 'def' en 'abcdef'. Voor een string van lengte n zijn er, wanneer uitsluitend niet-lege substrings worden geteld, precies n(n+1)/2 substrings. Als de lege substring wordt meegerekend komt daar één bij.

Relaties met andere concepten: een prefix is een substring die aan het begin van de string begint; een suffix is een substring die eindigt aan het einde van de string. Substrings verschillen van subsequences doordat substrings contiguï nt zijn.

Efficiëntie en technieken: een naïeve substringzoeking in een tekst van lengte n bij een patroon van lengte m kost O(nm). Geavanceerde algoritmen zoals Knuth–Morris–Pratt (KMP), Boyer–Moore en Rabin–Karp leveren snellere oplossing bij herhaaldelijk of grote datasets, vaak met tijdscomplexiteiten in O(n + m) of verwachte O(n + m). Voor meerdere substringqueries op een vaste tekst kunnen suffix-trees of suffix-arrays met bijbehorende LCP-structuren substrings in tijd O(m) per query mogelijk maken na preprocessing van O(n).

Toepassingen van substringen omvatten tekstverwerking, zoekmachines, data-analyse, patroonherkenning en bioinformatica, waar substrings worden gebruikt voor overeenkomsten, motifs en compressie.