Fast optimal algorithms for computing all the repeats in a string
Given a string x = x[1..n] on an alphabet of size a, and a threshold pmin = 1, we first describe a new algorithm PSY1 that, based on suffix array construction, computes all the complete nonextendible repeats in x of length p = pmin. PSY1 executes in Θ(n) time independent of alphabet size and is an o...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
PSC
2008
|
| Online Access: | http://www.stringology.org/event/2008/p15.html http://hdl.handle.net/20.500.11937/35833 |
Similar Items
Fast, Practical Algorithms for Computing All the Repeats in a String
by: Puglisi, Simon, et al.
Published: (2010)
by: Puglisi, Simon, et al.
Published: (2010)
Computing regularities in strings
by: Smyth, William, et al.
Published: (2009)
by: Smyth, William, et al.
Published: (2009)
An adaptive hybrid pattern-matching algorithm on indeterminate strings
by: Smyth, Bill, et al.
Published: (2009)
by: Smyth, Bill, et al.
Published: (2009)
How many runs can a string contain?
by: Puglisi, S., et al.
Published: (2008)
by: Puglisi, S., et al.
Published: (2008)
Faster algorithms for computing maximal multirepeats in multiple sequences
by: Iliopoulos, Costas, et al.
Published: (2009)
by: Iliopoulos, Costas, et al.
Published: (2009)
Fast pattern-matching on indeterminate strings
by: Holub, J., et al.
Published: (2008)
by: Holub, J., et al.
Published: (2008)
An adaptive hybrid pattern-matching algorithm on indeterminate strings
by: Smyth, Bill, et al.
Published: (2008)
by: Smyth, Bill, et al.
Published: (2008)
Fast algorithms for approximate circular string matching
by: Barton, C., et al.
Published: (2014)
by: Barton, C., et al.
Published: (2014)
A new approach to the periodicity lemma on strings with holes
by: Smyth, Bill, et al.
Published: (2009)
by: Smyth, Bill, et al.
Published: (2009)
Sorting suffixes of two-pattern strings
by: Franek, F., et al.
Published: (2004)
by: Franek, F., et al.
Published: (2004)
A taxonomy of suffix array construction algorithms
by: Puglisi, Simon, et al.
Published: (2007)
by: Puglisi, Simon, et al.
Published: (2007)
Suffix arrays: what are they good for?
by: Puglisi, Simon, et al.
Published: (2006)
by: Puglisi, Simon, et al.
Published: (2006)
New suffix array algorithms - linear but not fast?
by: Antonitio, A., et al.
Published: (2004)
by: Antonitio, A., et al.
Published: (2004)
Analysis of string matching compression algorithms
by: Nadarajan, Krishnaveny, et al.
Published: (2008)
by: Nadarajan, Krishnaveny, et al.
Published: (2008)
Strings
by: Soomro, Waseem Javaid, et al.
Published: (2011)
by: Soomro, Waseem Javaid, et al.
Published: (2011)
A simple fast hybrid pattern-matching algorithm
by: Smyth, William Fennell, et al.
Published: (2007)
by: Smyth, William Fennell, et al.
Published: (2007)
Rule-Based On-the-fly Web Spambot Detection Using Action Strings
by: Hayati, Pedram, et al.
Published: (2010)
by: Hayati, Pedram, et al.
Published: (2010)
A comparative analysis of algorithms for fast computation of Zernike moments
by: Chong, C
Published: (2003)
by: Chong, C
Published: (2003)
An efficient algorithm for fast computation of pseudo-Zernike moments
by: Chong, Chee-Way
Published: (2003)
by: Chong, Chee-Way
Published: (2003)
Lempel-Ziv factorization using less time & space
by: Chen, G., et al.
Published: (2008)
by: Chen, G., et al.
Published: (2008)
Inverted files versus suffix arrays for locating patterns in primary memory
by: Puglisi, Simon, et al.
Published: (2006)
by: Puglisi, Simon, et al.
Published: (2006)
Loop-based RSA Key Generation Algorithm using String Identity
by: Norhidayah, Muhammad, et al.
Published: (2013)
by: Norhidayah, Muhammad, et al.
Published: (2013)
Seven-part string
by: Kerr, Thor
Published: (2021)
by: Kerr, Thor
Published: (2021)
Methods of string class
by: Soomro, Waseem Javaid, et al.
Published: (2011)
by: Soomro, Waseem Javaid, et al.
Published: (2011)
A simple algorithm for computing the Lempel-Ziv factorization
by: Crochemore, M., et al.
Published: (2008)
by: Crochemore, M., et al.
Published: (2008)
Cover array string reconstruction
by: Crochemore, M., et al.
Published: (2010)
by: Crochemore, M., et al.
Published: (2010)
Improved particle swarm optimization by fast annealing algorithm
by: Bashath, Samar, et al.
Published: (2019)
by: Bashath, Samar, et al.
Published: (2019)
Enhance key generation algorithm based user string identity as public key
by: Norhidayah, Muhammad
Published: (2015)
by: Norhidayah, Muhammad
Published: (2015)
Application Of Exact String Matching Algorithms Towards SMILES Representation Of Chemical Structure.
by: Klaib, Ahmad Fadel, et al.
Published: (2007)
by: Klaib, Ahmad Fadel, et al.
Published: (2007)
Parallel Quick-Skip Search Hybrid Algorithm For The Exact String Matching Problem.
by: Naser, Mustafa Abdulsahib
Published: (2010)
by: Naser, Mustafa Abdulsahib
Published: (2010)
Dynamic key scheduling algorithm for block ciphers using quasigroup string transformation
by: Hassan Disina, Abdulkadir
Published: (2018)
by: Hassan Disina, Abdulkadir
Published: (2018)
Time-dependent searches for point sources of neutrinos with the 40-string and 22-string configurations of icecube
by: Abbasi, R., et al.
Published: (2012)
by: Abbasi, R., et al.
Published: (2012)
On the maximal number of cubic runs in a string
by: Crochemore, M., et al.
Published: (2010)
by: Crochemore, M., et al.
Published: (2010)
The tensile performance of r-PET bottle string: effects of different string sizes and cutting axes
by: Nasir, Khairani, et al.
Published: (2019)
by: Nasir, Khairani, et al.
Published: (2019)
Duality and decay of macroscopic F-strings
by: Skliros, Dimitri P., et al.
Published: (2013)
by: Skliros, Dimitri P., et al.
Published: (2013)
Statistical analysis, ciphertext only attack, improvement of generic quasigroup string transformation and dynamic string transformation
by: Hassan Disina, Abdulkadir, et al.
Published: (2018)
by: Hassan Disina, Abdulkadir, et al.
Published: (2018)
CMB constraints on cosmic strings and superstrings
by: Charnock, Tom, et al.
Published: (2016)
by: Charnock, Tom, et al.
Published: (2016)
Highly excited strings I: Generating function
by: Skliros, Dimitri P., et al.
Published: (2017)
by: Skliros, Dimitri P., et al.
Published: (2017)
Repeated eigenstructure assignment in the computation of friends of output-nulling subspaces
by: Ntogramatzidis, Lorenzo
Published: (2014)
by: Ntogramatzidis, Lorenzo
Published: (2014)
Optimization of fast fourier transform processor using genetic algorithm on Raspberry Pi
by: Ghazi, Firas Faisal, et al.
Published: (2019)
by: Ghazi, Firas Faisal, et al.
Published: (2019)