Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: prefix

Sortuj według:

Ogranicz wyniki do:

Analiza porównawcza algorytmów wyszukiwania wzorca w tekście

Widuch J.

Studia Informatica

2013

Vol. 34, nr 1

5--29

Jednym z problemów związanych z przetwarzaniem tekstów jest problem wyszukiwania wzorca w tekście, którego celem jest wyznaczenie wszystkich wystąpień w zadanym tekście innego tekstu, zwanego wzorcem. W niniejszej pracy dokonano analizy porównawczej istniejących algorytmów wyszukiwania wzorca w tekście, przy czym kryterium porównawczym jest czas wyszukiwania wzorca. Wyniki przeprowadzonych badań zamieszczono w pracy.

One of the text processing problems is the pattern matching problem. The goal of the problem is to find all places where one text or string, called pattern, is found within the given text. In this paper, a comparative analysis of existing string matching algorithms is presented, and the comparison criterion is the time of searching the pattern in the text. The results of the tests are also presented.

The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages

Rampersad N., Shallit J., Xu Z.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

223-236

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.