## Abstract

A repetition in a string of letters consists of exact concatenations of identical

factors of the string. Crochemore’s repetitions algorithm, usually also referred

to as Crochemore’s partitioning algorithm, was introduced in 1981, and was the

first optimal O(n log n)-time algorithm to compute all repetitions in a string of

length n. A weighted string is a string in which a set of letters may occur at each

position with respective probabilities of occurrence. In this article, we present a

new variant of Crochemore’s partitioning algorithm for weighted strings, which

requires optimal time O(n log n), thus improving on the best known O(n2)-time

algorithm for computing all repetitions in a weighted string of length n.

factors of the string. Crochemore’s repetitions algorithm, usually also referred

to as Crochemore’s partitioning algorithm, was introduced in 1981, and was the

first optimal O(n log n)-time algorithm to compute all repetitions in a string of

length n. A weighted string is a string in which a set of letters may occur at each

position with respective probabilities of occurrence. In this article, we present a

new variant of Crochemore’s partitioning algorithm for weighted strings, which

requires optimal time O(n log n), thus improving on the best known O(n2)-time

algorithm for computing all repetitions in a weighted string of length n.

Original language | English |
---|---|

Title of host publication | Proceedings of the 2nd International Conference on Algorithms for Big Data |

Editors | Costas S Iliopoulos, Alessio Langiu |

Publisher | King's College London |

Pages | 9-15 |

Number of pages | 7 |

Publication status | Published - 16 Apr 2014 |

Event | 2nd International Conference on Algorithms for Big Data - Italy, Palermo, United Kingdom Duration: 7 Apr 2014 → 9 Apr 2014 |

### Publication series

Name | CEUR Workshops Proceedings |
---|---|

ISSN (Electronic) | 1613-0073 |

### Conference

Conference | 2nd International Conference on Algorithms for Big Data |
---|---|

Country/Territory | United Kingdom |

City | Palermo |

Period | 7/04/2014 → 9/04/2014 |