CareerCup

you can use trie data structure. Time complexity will be O(N) for search.

Inverted index is what the question is about.

The question is essentially asking for a pattern matching algorithm. Knuth-Morris-Pratt is one popular one.

I think I myself have a solution.
Suppose we have to search the phrase "This is".
Then for every occurrence of "This" we will have a node in the trie with the index stored
Then we search for the word "is" in the trie, and hence we can find all the indices in which "is" occur in the large text
Then for each index at which "is" occurs, we can check in O(m+n) time { all the indices at which index of occurrence of "is" - length of("the ") } which matches with the indices at which "the" occurs.
where m,n- number of indices at which "the" , "is" occur respectively.
This approach can be extended to phrases with more than two words in this manner-
For e.g.- we have to search "This is a good approach"
We keep all the indices at which "This is" occurred in a set say S. Then we match all indices at which "a" occurs and match it in the above mentioned manner for all the indices in S and continue so on

public class Solution{
	
private static Node rt=new Node();//Reference to root node of trie.
public static boolean searchWord(String wrd){
	if(wrd==null||wrd.length()==0){
		return false;
	}
	for(int i=0;i<wrd.length();i++){
		int idx=(int)wrd.charAt(i)-'a';
		Node v=rt;
		if(v.nextLetters[idx]==null){
			return false;
		}
		v=v.nextLetters[idx];
	}
	return true;
	
}

public static boolean searchPhrase(String[] phrase){
	
	Node v=rt;
	for(int i=0;i<phrase[0].length();i++){
		int idx=(int)phrase[0].charAt(i)-'a';
		if(v.nextLetters[idx]==null){
			return false;
		}
		v=v.nextLetters[idx];
	}
	for(int i=1;i<phrase.length;i++){
		String wrd=phrase[i];
		
		//check if the node corresponding to the last letter of the previous word has a pointer to the first letter of the current word
		int currChar=(int)wrd.charAt(0)-'a';
		if(r.c[currChar]==null || v.nextWordStart[currChar]==null){
			return false;
		}
		v=r.c[currChar];
		for(int j=1;j<wrd.length();j++){
			currChar=wrd.charAt(j)-'a';
			if(v.nextLetter[currChar]==null){
				return false;
			}
			v=v.nextLetter[currChar];
		}
	}
	return true;
}



//represents a letter.
private static class Node{
	Node[] nextLetters;//Points to the next character of current word
	Node[] nextWordStart;//Points to starting character of next word (if node is the last letter of a word in a phrase).
	
	public Node(){
		nextLetters=new Node[26];
		nextWordStart=new Node[26];
	}
}

}

Inverted index is what the question is about.