TY - GEN
T1 - An improvement of the franek-jennings-smyth pattern matching algorithm
AU - Kobayashi, Satoshi
AU - Hendrian, Diptarama
AU - Yoshinaka, Ryo
AU - Shinohara, Ayumi
N1 - Funding Information:
This work is partially supported by JSPS KAKENHI Grant Numbers JP19K20208 and JP15H05706.
Publisher Copyright:
© Proceedings of the Prague Stringology Conference, PSC 2019. All rights reserved.
PY - 2019
Y1 - 2019
N2 - In this paper, we propose a new pattern matching algorithm based on the Franek-Jennings-Smyth (FJS) algorithm. The FJS algorithm is a hybrid of the Knuth- Morris-Pratt (KMP) and the Sunday algorithms. The worst case time complexity of the KMP algorithm is linear time and the Sunday algorithm is quadratic time. However, the Sunday algorithm is faster than the KMP algorithm in practice. Inheriting the virtues of those algorithms, the FJS algorithm runs in linear time in the worst case and fast in practice. We improve the FJS algorithm by further taking an idea inspired by the Quite-Naive algorithm by Cantone and Faro. The experimental results show that our algorithm is faster than the FJS algorithm in general except when a pattern is extremely short.
AB - In this paper, we propose a new pattern matching algorithm based on the Franek-Jennings-Smyth (FJS) algorithm. The FJS algorithm is a hybrid of the Knuth- Morris-Pratt (KMP) and the Sunday algorithms. The worst case time complexity of the KMP algorithm is linear time and the Sunday algorithm is quadratic time. However, the Sunday algorithm is faster than the KMP algorithm in practice. Inheriting the virtues of those algorithms, the FJS algorithm runs in linear time in the worst case and fast in practice. We improve the FJS algorithm by further taking an idea inspired by the Quite-Naive algorithm by Cantone and Faro. The experimental results show that our algorithm is faster than the FJS algorithm in general except when a pattern is extremely short.
KW - Exact pattern matching
KW - Knuth-Morris-Pratt algorithm
KW - Sunday algorithm
UR - http://www.scopus.com/inward/record.url?scp=85081651161&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081651161&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85081651161
T3 - Proceedings of the Prague Stringology Conference, PSC 2019
SP - 56
EP - 68
BT - Proceedings of the Prague Stringology Conference, PSC 2019
A2 - Holub, Jan
A2 - Zdarek, Jan
PB - Prague Stringology Club
T2 - 23rd Prague Stringology Conference, PSC 2019
Y2 - 26 August 2019 through 28 August 2019
ER -