Fuzzy String Matching Using a Prefix Table


  • Armen H. Kostanyan Yerevan State University




KMP algorithm, Approximate string matching, Fuzzy string matching


The string matching problem (that is, the problem of finding all occurrences of a pattern in the text) is one of the well-known problems in symbolic computations with applications in many areas of artificial intelligence. The most famous algorithms for solving it are the finite state machine method and the Knuth-Morris-Pratt algorithm (KMP). In this paper, we consider the problem of finding all occurrences of a fuzzy pattern in the text. Such a pattern is defined as a sequence of fuzzy properties of text characters. To construct a solution to this problem, we introduce a two-dimensional prefix table, which is a generalization of the one-dimensional prefix array used in the KMP algorithm.


R. S. Boyer and J. S. Moore, “A fast string matching algorithm,” Association for Computing Machinery, vol. 20, no. 10, pp. 762-772, 1977.

D. Knuth and M. Pratt, “Fast pattern matching in strings,” SIAM J. Comput. vol. 6, no. 2, pp. 323-350, 1977.

G. Landau and U. Vishkin, “Efficient string matching with k mismatches,” TCS, vol. 43, pp. 239-249, 1986.

R. Baeza-Yates and N. Gonzaio, “A faster algorithm for approximate string matching,” in Proc. of Seventh Annual Symp. Combinatorial Pattern Matching, Spinger-Verlag, 1996, pp. 1-23.

B. Smyth, “Computing Patterns in Strings”, Addison-Wesley UK, 2003.

A. Kostanyan, “Fuzzy String Matching with Finite Automata”, in Proceedings on 2017 IEEE Conference CSIT-2017, Yerevan, Armenia, pp. 25-29. IEEE Press, USA 2018.

L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning-I,” Information Sciences, vol. 8, pp. 199-249, 1975.




How to Cite

Kostanyan, A. H. . (2020). Fuzzy String Matching Using a Prefix Table. Mathematical Problems of Computer Science, 54, 116–121. https://doi.org/10.51408/1963-0065