## String Indexing for Patterns With Wildcards

Publication: Research - peer-review › Article in proceedings – Annual report year: 2012

We consider the problem of indexing a string t of length n to report the occurrences of a query pattern p containing m characters and j wildcards. Let occ be the number of occurrences of p in t, and σ the size of the alphabet. We obtain the following results. - A linear space index with query time O(m + σj log log n + occ). This significantly improves the previously best known linear space index by Lam et al. [ISAAC 2007], which requires query time Θ(jn) in the worst case. - An index with query time O(m + j + occ) using space O(σk2 n log k log n), where k is the maximum number of wildcards allowed in the pattern. This is the first non-trivial bound with this query time. - A time-space trade-off, generalizing the index by Cole et al. [STOC 2004]. Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.

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

Title of host publication | Algorithm Theory – SWAT 2012 : 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings |

Editors | Fedor V. Fornin, Petteri Kaski |

Publisher | Springer |

Publication date | 2012 |

Pages | 283-294 |

ISBN (print) | 978-3-642-31154-3 |

ISBN (electronic) | 978-3-642-31155-0 |

DOIs | |

State | Published - 2012 |

Event | 13th Scandinavian Symposium and Workshops on Algorithm Theory - Helsinki, Finland |

### Conference

Conference | 13th Scandinavian Symposium and Workshops on Algorithm Theory |
---|---|

???event.location??? | University of Helsinki |

Country | Finland |

City | Helsinki |

Period | 04/07/2012 → 06/07/2012 |

Name | Lecture Notes in Computer Science |
---|---|

Volume | 7357 |

ISSN (Print) | 0302-9743 |

Citations | Web of Science® Times Cited: No match on DOI |
---|

Download as:

Loading map data...

ID: 10214522