CareerCup

Build separate suffix trees for author, name and publisher.
Insert all the suffixes of all the authors in the first suffix tree. Do the same for name and publisher. Here suffix trees are useful because:

* Suffix trees facilitate partial string matching.
* We can match the pattern in O(p) time, where p is the length of the pattern.
* They take linear extra space.

Partial string matching can be done as explained below.
Every substring of a given string is a prefix of one of its suffix. So we search the given query string starting from the root and match until the input is exhausted. Suppose we reach a node n. Then go to every leaf from node n and add that string to the list of suggestions.

There exists an online linear time construction algorithm for suffix trees, known as Ukkonen's algorithm

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class test5BookSearch {

public static void main (String[] args){
HashMap<Integer, String> BookDetail = new HashMap<Integer, String>();
HashMap<Integer, String> BookDetail2 = new HashMap<Integer, String>();
BookDetail.put(1, "JavaFlavours,JohnnyDepp,Oreilly,2005,51.66,620");
BookDetail.put(2, "Programming with java,Clara,Pearson,2006,95.25,350");
BookDetail.put(3, "Let Us java,Sami Shaio,Apress,2009,68.99,562");
BookDetail.put(4, "Oracle Certified java,Orca Starbuck,Oracle,2011,102.52,105");
BookDetail.put(5, "Java 7 Essentials,John wiley,Sybex,2012,98.00,56");
BookDetail2.putAll(BookDetail);
List<String> details = new ArrayList<String>();
for(int i =0;i<BookDetail.size() ; i++){
String Value = BookDetail.get(i+1);
String[] Values = Value.split(",", -1);
for(int j=0;j<3 ;j++ ){
details.add(Values[j]);
}
}

String search = "a";
for(int k =0; k<details.size() ;k++ ){
String getValue = details.get(k);
if(getValue.contains(search)){
int index = details.indexOf(getValue);
index = index/3 ;
String Line ="" ;
Line = BookDetail2.get(index + 1);
if(Line != null){
String[] LineValues = Line.split(",",-1);
System.out.println("\nName :" +LineValues[0]);
System.out.println("Author :" +LineValues[1]);
System.out.println("Publisher :" +LineValues[2]);
System.out.println("Year :" +LineValues[3]);
System.out.println("Price :" +LineValues[4]);
System.out.println("Inventory :" +LineValues[5]);
BookDetail2.remove(index + 1);
}
}
}

}
}


Can change the "search" string or can pass it as argument too.

#Python, and works great
def field_indexer(index, field, string, book_id):
    try:
        field_index = index[field]
    except:
        index[field] = {}
        field_index = index[field]
    for token in string.split():
        token = token.strip().lower()
        try:
            field_index[token].add(book_id)
        except:
            field_index[token] = set()
            field_index[token].add(book_id)
    return index


def search_field(index, field, query):
    field_index = index[field]
    matched_ids = set()
    for token in query.split():
        token = token.strip().lower()
        try:
            matched_ids = matched_ids | field_index[token]
        except:
            #lets do partial search if there is no whole word
            for key in field_index.keys():
                if token in key:
                    matched_ids = matched_ids | field_index[key]
    return matched_ids

catalog = list()
catalog.append({"name": "Politics in your pants",
                "author": "Rahul Gandhi",
                "publisher": "Congress"})

index = dict()
book_id = 0

#indexing done hre
for book in catalog:
    for field, value in book.iteritems():
        index = field_indexer(index, field, value, book_id)
    book_id += 1

#query here
for id in search_field(index, field="author", query="Rahul G"):
    print catalog[id]