AdvOL Student Seminars and Defences
Michael Liut, March 28, 2019, 15:30-16:30, ITB 201
Speaker:   Michael Liut
Department of Computing and Software
McMaster University

Title:  Computing Lyndon Array
Read more...
 
AdvOL Optimization Seminars
Dalibor Froncek, March 28, 2019, 16:30-17:30, ITB 201
Speaker:   Dalibor Froncek
Department of Mathematics and Statistics
University of Minnesota Duluth

Title:  Magic type labelings of cycle products
Read more...
 
Fields Institute Industrial Optimization Seminar, March 19, 2019
Speakers:   Merve Bodur (University of Toronto)
Imre Polik (SAS Institute)

The Industrial Optimization Seminar is held at the Fields Institute. See the seminar series website for further information.
 
Home
Saturday, 20 April 2019
 
 
Main Menu
Home
People
Publications
Software
Events
Awards
Photogallery
Internal pages
Latest Theses
File Icon Novel Stochastic Programming Formulations for Assemble-to-Order Systems
File Icon Computational Determination of the Largest Lattice Polytope Diameter
File Icon Computational Framework for the Generalized Berge Sorting Conjecture
Latest Reports
Visitors by region
Totals Top 20
 59 % Unknown
 15 % Commercial
 9 % networks
 5 % Canada
 3 % Germany
 2 % Russia
 2 % China
 < 1.0 % Brazil
 < 1.0 % Educational
 < 1.0 % 
 < 1.0 % Poland
 < 1.0 % Ukraine
 < 1.0 % United Kingdom
 < 1.0 % Italy
 < 1.0 % France
 < 1.0 % India
 < 1.0 % Netherlands
 < 1.0 % Japan
 < 1.0 % Organization
 < 1.0 % Australia

Visitors: 5990112
Michael Liut, March 28, 2019, 15:30-16:30, ITB 201
Speaker:   Michael Liut
Department of Computing and Software
McMaster University

Title:  Computing Lyndon Array

Abstract: All runs in a string can be computed in linear time. To do so, the Lempel-Ziv factorization of the input string must be computed as the first step. In 2015, Banai et al. presented a different algorithm that requires first to compute the Lyndon array for a given ordering of the alphabet and its inverse. To our knowledge, it is the only algorithm not requiring the Lempel-Ziv factorization. Thus, it is important to know how hard or easy it is to compute the Lyndon array. A Lyndon array for a given string x and a given order of the alphabet is an integer array L such that L[i] = the length of the longest Lyndon substring of x starting at position i. We discuss a well-know approach based on sorting suffixes, computing the inverse of the suffix array, and applying the NSV (next smaller value) algorithm. There are several known algorithms of O(n log n) and O(n^2) worst case complexity we present; we include our novel O(n log n) algorithm as well. Then we discuss our elementary linear algorithm based on Baier’s method for sorting suffixes. We present the CPU time results of executions of some of these algorithms on a wide variety of input strings and analyze the results.
 
Next >
McMaster University
McMaster University
Faculty of Engineering
Faculty of Engineering
Faculty of Science
Faculty of Science
Computing & Software
Computing & Software
Comput. Eng. & Sci.

School Website >>>


Latest Publications
Publication Downloads
Error cannot find GD extension
 
Top!
Top!