Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Comparing Degenerate Strings

Alzamel Mai, Ayad Lorraine A. K., Bernardini Giulia, Grossi Roberto, Iliopoulos Costas S., Pisanti Nadia, Pissis Solon P., Rosone Giovanna

Fundamenta Informaticae

2020

Vol. 175, nr 1-4

41--58

Uncertain sequences are compact representations of sets of similar strings. They highlight common segments by collapsing them, and explicitly represent varying segments by listing all possible options. A generalized degenerate string (GD string) is a type of uncertain sequence. Formally, a GD string Ŝ is a sequence of n sets of strings of total size N, where the ith set contains strings of the same length ki but this length can vary between different sets. We denote by W the sum of these lengths k0, k1, . . . , k n-1. Our main result is an 𝒪(N + M)-time algorithm for deciding whether two GD strings of total sizes N and M, respectively, over an integer alphabet, have a non-empty intersection. This result is based on a combinatorial result of independent interest: although the intersection of two GD strings can be exponential in the total size of the two strings, it can be represented in linear space. We then apply our string comparison tool to devise a simple algorithm for computing all palindromes in Ŝ in 𝒪(min{W , n 2}N )-time. We complement this upper bound by showing a similar conditional lower bound for computing maximal palindromes in Ŝ. We also show that a result, which is essentially the same as our string comparison linear-time algorithm, can be obtained by employing an automata-based approach.

Identification of fingerprints using circular string approximation for mobile devices

Ajala Oluwole I., Iliopoulos Costas S., Khan Mujibur R.

Annals of Computer Science and Information Systems

2017

Vol. 13

193--197

Lately, Biometrics has employed the use of fingerprints to identify individuals. Out of the commonly used techniques, fingerprint authentication till date, remains the most reliable. The bulk of research that has focused on fingerprint authentication, has however, neglected the issues that arise with fingerprints resulting to incorrect orientation identification. This is because it is assumed and often times wrongly, that the direction of the fingerprint will align with the stored fingerprint image. This singular issue poses tension in fingerprint matching, which only a negligible number of techniques have considered. As computers and mobile devices adopt fingerprint recognition as a way to authenticate user, this apparent tension gains more popularity, becoming an integral research area which must be addressed.