TY - GEN
T1 - Fast and simple circular pattern matching
AU - Susik, Robert
AU - Grabowski, Szymon
AU - Deorowicz, Sebastian
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - The problem of circular pattern matching is to find all rotations of a given pattern P in text T, both over a common alphabet. The pattern and any of its rotations are also called conjugates in the literature. For the online version of this problem we present a new general approach and use several matching techniques as components, based on bit-parallelism and filtering. The experimental results show the effectiveness of the method, with matching speeds reaching 7–8GB/s for long patterns and natural language or protein data.
AB - The problem of circular pattern matching is to find all rotations of a given pattern P in text T, both over a common alphabet. The pattern and any of its rotations are also called conjugates in the literature. For the online version of this problem we present a new general approach and use several matching techniques as components, based on bit-parallelism and filtering. The experimental results show the effectiveness of the method, with matching speeds reaching 7–8GB/s for long patterns and natural language or protein data.
KW - Circular pattern matching
KW - Combinatorial problems
KW - String algorithms
UR - https://www.scopus.com/pages/publications/84903709790
U2 - 10.1007/978-3-319-02309-0_59
DO - 10.1007/978-3-319-02309-0_59
M3 - Conference contribution
AN - SCOPUS:84903709790
T3 - Advances in Intelligent Systems and Computing
SP - 537
EP - 544
BT - Man-Machine Interactions 3
A2 - Gruca, Aleksandra
A2 - Czachórski, Tadeusz
A2 - Kozielski, Stanisław
A2 - Czachórski, Tadeusz
PB - Springer Verlag
T2 - 3rd International Conference on Man-Machine Interactions, ICMMI 2013
Y2 - 22 October 2013 through 25 October 2013
ER -