Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Character frequency-based approach for searching for substrings of circular patterns and their conjugates in online text

Tytuł:
Character frequency-based approach for searching for substrings of circular patterns and their conjugates in online text
Autorzy:
Prasad, Vinod
Powiązania:
https://bibliotekanauki.pl/articles/2097972.pdf
Data publikacji:
2021
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
pattern matching in strings
circular pattern matching
similarity search
substring search
Źródło:
Computer Science; 2021, 22 (2); 235-250
1508-2806
2300-7036
Język:
angielski
Prawa:
CC BY: Creative Commons Uznanie autorstwa 4.0
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
A fundamental problem in computational biology is dealing with circular patterns. The problem consists of finding a pattern and its rotations in a database. In this paper, we present two online algorithms. The first algorithm reports all of the substrings (factors) of a given pattern in an online text. Then, without losing efficiency, we extend the algorithm to process the circular rotations of the pattern. For a given pattern P of size M and a text T of size N, the extended algorithm reports all of the locations in the text where a substring of Pc is found where Pc is one of the rotations of P. For an alphabet size σ using O(M) space, the desired goals are achieved in an average O(MN/σ) time, which is O(N) for all patterns with length M ≤ σ. Traditional string-processing algorithms make use of advanced data structures such as suffix trees and automaton. The experimental results we have provided show that basic data structures such as arrays can be used in text-processing algorithms without compromising efficiency.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies