article · 2000

Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf

Kimmo Fredriksson

Cited by 0Abstract and details only

Abstract

Given a text string T of lenght n and a pattern string P of lenght m over some alphabet Σ, we want to find the occurrences of P ′ from T such that P ′ can be derived from P by set of local swaps, i.e. transpositions of two adjacent characters, each character swapping at most once. We give several simple but fast algorithms for the problem. The first algorithm is based on Boyer–Moore–Horspool approach. The second algorithm uses a nondeterministic finite automaton that is simulated using a shift–or type method. We improve the shift–or to take only time O(n / log |Σ | s⌈(m + 1)/w⌉), where s ≥ |Σ | is the space usage of the algorithm, and w is the lenght of the machine word. This algorithm is sublinear for small patterns and alphabets, and is asymptotically the fastest bit–parallel simulation of sufficiently simple nondeterministic finite automata. Finally, we show how bit–parallel suffix automaton can be used to solve the problem in optimal average time O(n log m/m), while being only O(n⌈m/w⌉) in the worst case. The algorithms are very simple to implement, and experimental results show that they are very fast on natural language.

Cite this paper

APA 7

Fredriksson, K. (2000). Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf.

MLA 9

Fredriksson, Kimmo. “Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf.” 2000.

Chicago

Fredriksson, Kimmo. 2000. “Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf.”

Harvard

Fredriksson, K. (2000) ‘Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf’.

BibTeX

@article{fredriksson2000fast,
  title = {{Fast algorithms for string matching with and without swaps. Unpublished manuscript, http://www.cs.uku.fi/~fredriks/pub/ papers/sm-w-swaps.pdf}},
  author = {Fredriksson, Kimmo},
  year = {2000}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.