Home

Welcome to the prefixMatching wiki!

here is the specification:

Given a collection S = {S1 , S2 , ..., Sn } of strings and a Pattern string P , write a program to print all strings Si ∈ S such that P is a prefix of Si using following two approaches:
* String collection S is maintained as an array of strings and binary search is em- ployed to obtain all strings Si ∈ S such that P is a prefix of Si . * String collection S is maintained as a “trie” data structure and tree navigation is used to obtain all strings Si ∈ S such that P is a prefix of Si .

Also compare the two approaches for index space and query time. * Input: Program should first accept file prefix data.txt which has a collection S of strings with one string on each line and then repeatedly asks for a Pattern P . * Output: Your program should print the space required for the two approaches for a given string collection S. Also output all strings in S with P as a prefix and the time required to obtain them for both approaches.