k-Abelian Pattern Matching

Two words are called \(k\)-abelian equivalent, if they share the same multiplicities for all factors of length at most \(k\). We present an optimal linear time algorithm for identifying all occurrences of factors in a text that are \(k\)-abelian equivalent to some pattern. Moreover, an optimal algorithm for finding the largest \(k\) for which two words are \(k\)-abelian equivalent is given. Solutions for various online versions of the \(k\)-abelian pattern matching problem are also proposed.

Logo BII

BII

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:Keine Creative-Commons-Lizenz - Es gelten die Bestimmungen des dt. Urheberrechts (UrhG)Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.