Category Archives: algorithms

algorithms and other computer science stuff

Algorithm to determine whether two strings are circular permutations of each other

A recent question on the string matching assignment sheet for the students: Design an algorithm that determines for two strings S and T (of equal length m)whether they are circular (or cyclic) permutations of each other. So what is a … Continue reading

Posted in algorithms, Bioinformatics, Science | Tagged , , , , | 1 Comment

The Rabin-Karp string matching algorithm

The Rabin-Karp algorithm solves the string matching problem I described in an earlier post. Its worst-case running time is the same as for the naive string matching algorithm, but it performs significantly better on real-word inputs on average. (Note that … Continue reading

Posted in algorithms, Bioinformatics, Science | Tagged , , , , , | Leave a comment

Naive string matching

Note: This is an article in the string matching series. You can read the introduction to string matching here. All elaborated and fast string matching algorithms perform some kind of preprocessing to gain information on the pattern. This information is … Continue reading

Posted in algorithms, Bioinformatics, Science | Tagged , , , , | 1 Comment

Algorithms for string matching

String matching I am responsible for a tutorial on Algorithms and Models in Computational Biology this semester, so I decided to write a bit about some of the algorithms here when ever I find the time. The posts here intentionally … Continue reading

Posted in algorithms, Bioinformatics, Science | Tagged , , , | 2 Comments