T-106.290 Ohjelmoinnin laboratoriotyöt

Subject: String search (3 or 4 cr)

NOTE: This topic has been fully booked.

The purpose of this topic is to study the performance of string searching algorithms on different inputs: random bytes, plain english/finnish text, or some semi-natural data such as binary executables or IP packets. Both the kind of strings to be searched and data to search from vary. Test also with different alphabets than normal 8-bit bytes.

3 cr version

Study the following string searching algorithms:

• Brute-Force searching
• Knuth-Morris Pratt
• Boyer-Moore
• Rabin-Karp

4 cr version

Study the following string searching algorithms used more widely in practice:

• Knuth-Morris-Pratt
• Boyer-Moore-Horspool
• Hume-Sunday: SFC / SLFC
• Hume-Sunday: Fast Boyer-Moore

References

References in addition to generic literature in algorithms and Internet:

• Cormen, Leiserson, Rivest:  Introduction to algorithms
• Sedgewick:  Algorithms / Algorithms in C / Algorithms in C++